Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On the Rank of Mixed 0,1 Polyhedra

Gérard CornuéjolsContact Information and Yanjun LiContact Information

(6)  Graduate School of Industrial Administration Carnegie Mellon University, Pittsburgh, USA
Abstract
Eisenbrand and Schulz showed recently (IPCO 99) that the maximum Chvátal rank of a polytope in the [0,1]n cube is bounded above by O(n 2 logn) and bounded below by (1 + ∈)n for some ∈ < 0. It is well known that Chvátal’s cuts are equivalent to Gomory’s fractional cuts, which are themselves dominated by Gomory’s mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory’s 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. We relate this result to bounds on the disjunctive rank and on the Lovász-Schrijver rank of polytopes in the [0,1]n cube. The result still holds for mixed 0,1 polyhedra with nn binary variables.
Supported by NSF grant DMI-9802773 and ONR grant N00014-97-1-0196.

Contact Information Gérard Cornuéjols
Email: fgcov@andrew.cmu.edu

Contact Information Yanjun Li
Email: yanjung@andrew.cmu.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)