Gomory integer programs (Q1424270): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2004100370 / rank | |||
Normal rank |
Revision as of 00:56, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gomory integer programs |
scientific article |
Statements
Gomory integer programs (English)
0 references
11 March 2004
0 references
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)].
0 references
integer programming
0 references
Gomory family
0 references
group relaxation
0 references
total dual integral
0 references
normal matrix
0 references
regular subdivision
0 references