.png){kind=icon}
返回
Efficient branching rules for optimizing range and order-based objective functions
.png){kind=icon}
PRE
AI
DOI：10.1007/s10107-025-02306-0.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑具有指数数量变量的范围最小化问题，这些问题在公平性导向或双目标优化中经常出现。虽然分支定价方法在解决具有大量变量的成本导向型问题方面是成功的，但经典分支定价算法在解决范围最小化问题时的性能因线性规划松弛的松弛性较弱而受到显著影响。我们提出了范围分支（range branching），这是一种通用的分支规则，可以直接解决这一问题，并且可以在问题特定的分支方案之上使用。我们展示了范围分支的多个理想属性，并通过公平容量车辆路径问题和公平广义分配问题的一系列实例证明了其有效性。范围分支在计算时间、最优性间隙和分支定界树大小方面显著优于多种经典分支方案，使我们能够比传统方法解决更多的大型实例。此外，我们还展示了范围分支如何成功地推广到基于顺序的目标函数，例如基尼偏差。
Keyword:
Range minimization
Branch and price
Vehicle routing
Generalized assignment
Fairness
期刊
M
IF:
2.5
论文数:
93
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容