Branch-and-cut for linear programs with overlapping SOS1 constraints
Branch-and-cut for linear programs with overlapping SOS1 constraints
复制标题
DOI：
10.1007/s12532-017-0122-5
复制
发表时间：
2017-06
影响因子：
6.3
通讯作者：
Tobias Fischer;M. Pfetsch
中科院分区：
文献类型：
--
作者：
Tobias Fischer;M. Pfetsch
SOS1约束要求给定的一组变量中最多有一个是非零的。本文研究了一种求解带SOS1约束的线性规划的分枝割算法。我们关注SOS1约束重叠的情况。例如，可以在算法上利用相应的冲突图来改进分支规则、预处理、原始启发式算法和切割平面。在一项广泛的计算研究中，我们在三个不同应用程序的实例上评估了我们实现的组件。我们还通过与混合整数规划的解进行比较，证明了该方法的有效性，如果SOS1约束中的变量是有界的。
SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, preprocessing, primal heuristics, and cutting planes. In an extensive computational study, we evaluate the components of our implementation on instances for three different applications. We also demonstrate the effectiveness of this approach by comparing it to the solution of a mixed-integer programming formulation, if the variables appearing in SOS1 constraints ar bounded.