Gomory integer programs (Q1424270): Difference between revisions

For the parametric integer programming problem \(\text{IP}_{A,c}(b) = \min \{c^Tx : Ax=b, x \geq 0, x \text{ integral}\}\) with varying right hand sides the authors consider all group relaxations induced by faces of the regular subdivision of \(\text{cone}(A)\) induced by \(c\). Each of these faces determines a set of variables, and the corresponding group relaxation is the integer program where the nonnegativity constraints have been removed on these variables. A family of integer programs \(\text{IP}_{A,c}\) is a Gomory family if each of its members can be solved by one of its group relaxations. Among the main results of this paper is a characterzation of Gomory families. This characterization is applied to special families coming from total dual integral systems and so-called normal matrices. The paper concludes with a review of the corresponding structures (Gröbner bases etc.) from commutative algebra [\textit{B. Sturmfels}, Gröbner bases and convex polytopes, (University Lecture Series. 8. Providence, RI: American Mathematical Society) (1996; Zbl 0856.13020)].