Carnegie Mellon University
Browse

On the Rank of Mixed 0,1 Polyhedra

Download (198.6 kB)
journal contribution
posted on 2009-02-10, 00:00 authored by Gerard CornuejolsGerard Cornuejols, Yanjun Li
For a polytope in the [0, 1]n cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n2logn) and bounded below by (1 + ∈)n for some ∈ > 0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.

History

Date

2009-02-10

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC