Information-based branching schemes for binary linear mixed integer problems
Information-based branching schemes for binary linear mixed integer problems
复制标题
二元线性混合整数问题的基于信息的分支方案
DOI：
--
复制
发表时间：
2009
影响因子：
6.3
通讯作者：
M. Savelsbergh
中科院分区：
文献类型：
--
作者：
F. Kılınç;G. Nemhauser;M. Savelsbergh
分支变量的选择可以极大地影响分支定界算法的有效性和效率。分支变量选择的传统方法依赖于估计候选变量对目标函数的影响。我们提出了一种方法，该方法通过利用预先从不完整的分支定界树收集的一系列已发现的子问题中包含的信息来实现。特别是，我们使用这些信息来定义新的分支规则，以降低发生不适当分支的风险。我们提供的计算结果证明了新分支规则在各种基准实例上的有效性。
Branching variable selection can greatly affect the effectiveness and efficiency of a branch-and-bound algorithm. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We propose an approach which is empowered by exploiting the information contained in a family of fathomed subproblems, collected beforehand from an incomplete branch-and-bound tree. In particular, we use this information to define new branching rules that reduce the risk of incurring inappropriate branchings. We provide computational results that demonstrate the effectiveness of the new branching rules on various benchmark instances.