Gomory integer programs (Q1424270)

From MaRDI portal
Revision as of 23:13, 11 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Gomory integer programs
scientific article

    Statements

    Gomory integer programs (English)
    0 references
    0 references
    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
    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

    Identifiers