Generalized mixed integer rounding inequalities: facets for infinite group polyhedra
Generalized mixed integer rounding inequalities: facets for infinite group polyhedra
复制标题
广义混合整数舍入不等式：无限群多面体的面
作者：
Kiavash Kianfar;Y. Fathi
本文推广了混合整数舍入（MIR）方法，用于生成混合整数规划（MIP）问题的有效不等式。对于任意正整数n，我们对某（n + 1）维单约束多面体按顺序展开了n个面。然后我们表明，对于任何n，这些面中的最后一个面（我们称之为n步MIR面）可用于为一般（混合）IP约束的可行集生成一系列有效不等式，我们称之为n步MIR不等式。Gomory混合整数切割和Dash和g<s:1> nl<e:1> k（数学程序105(1):29-53,2006）的2步MIR不等式分别是n = 1,2对应的前两个族。n步MIR不等式很容易用周期函数产生，我们称之为n步MIR函数。在整个时期内，这些职能中没有一个是支配另一个的。最后，我们证明了n步MIR不等式对无限群多面体产生双斜率面，因此具有潜在的强性。
We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.