Gomory integer programs (Q1424270): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    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