Combinatorial benders' cuts for mixed-integer linear programming
Combinatorial benders' cuts for mixed-integer linear programming
复制标题
DOI：
10.1287/opre.1060.0286
复制
发表时间：
2006-07-01
影响因子：
2.7
通讯作者：
Fischetti, Matteo
中科院分区：
文献类型：
--
作者：
Codato, Gianni;Fischetti, Matteo
混合整数规划（MIPs）涉及通过大M系数建模的逻辑含义，是众所周知的最难解决的问题之一。在本文中，我们提出了一个自动的问题，并分析计算相当普遍的适用性，旨在消除模型依赖于大M系数。我们的解决方案定义了一个主整数线性问题（ILP），没有连续变量，其中包含组合信息的可行的整数变量组合，可以从原始MIP模型“蒸馏”。主解决方案被发送到从线性程序（LP），其验证它们并可能返回组合不等式以添加到当前主ILP。这些不等式与线性系统的极小（或不可约）不可行子系统相关联，当主解为整数时，这些不等式可以有效地分离。整体的解决方案机制非常类似于Benders的机制，但我们产生的切割是纯粹的组合，不依赖于MIP公式中使用的大M值。这产生了主问题的LP松弛，其可以比与原始MIP制剂相关联的问题紧密得多。两个特定类别的难以解决的MIP的计算结果表明，新的方法产生了一个重新制定，可以解决一些数量级的速度比原来的MIP模型。
Mixed-integer programs (MIPs) involving logical implications modeled through big-M coefficients are notoriously among the hardest to solve. In this paper, we propose and analyze computationally an automatic problem reformulation of quite general applicability, aimed at removing the model dependency on the big-M coefficients. Our solution scheme defines a master integer linear problem (ILP) with no continuous variables, which contains combinatorial information on the feasible integer variable combinations that can be "distilled" from the original MIP model. The master solutions are sent to a slave linear program (LP), which validates them and possibly returns combinatorial inequalities to be added to the current master ILP. The inequalities are associated to minimal (or irreducible) infeasible subsystems of a certain linear system, and can be separated efficiently in case the master solution is integer. The overall solution mechanism closely resembles the Benders' one, but the cuts we produce are purely combinatorial and do not depend on the big-M values used in the MIP formulation. This produces an LP relaxation of the master problem which can be considerably tighter than the one associated with original MIP formulation. Computational results on two specific classes of hard-to-solve MIPs indicate that the new method produces a reformulation which can be solved some orders of magnitude faster than the original MIP model.