Bound reduction using pairs of linear inequalities
Bound reduction using pairs of linear inequalities
复制标题
使用线性不等式对进行界限约简
DOI：
--
复制
发表时间：
2012
影响因子：
1.8
通讯作者：
P. Belotti
中科院分区：
文献类型：
--
作者：
P. Belotti
我们描述了一个过程，以减少混合整数非线性规划（MINLP）以及混合整数线性规划（MILP）问题的变量界限。该程序的工作原理是结合对不等式的线性规划（LP）松弛的问题。这个界减少过程扩展了可行性的边界减少技术的线性函数，在MINLP和MILP中使用。然而，它也可以被看作是一个特殊的情况下，最优性为基础的界减少，一种方法来推断变量的界限从LP松弛的问题。对于一个有m个约束和n个变量的LP松弛，有O（m2）对约束，我们的界约简方案的简单实现对于每对约束都有O（n3）的复杂性。因此，它的总复杂度O（m2n3）对于相对较大的问题可能是禁止的。我们已经开发了一个更有效的程序，具有复杂性O（m2n2），并将其嵌入到两个开源的求解器：一个MINLP和一个MILP。我们提供的计算结果证实了这种约束减少技术的几个实例的有用性。
We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m2) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n3) for each pair. Therefore, its overall complexity O(m2n3) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m2n2), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.