On the Rank of Mixed 0,1 Polyhedra

Abstract

For a polytope in the [0; 1]n cube, Eisenbrand and Schulz showed recently that the maximum Chvatal rank is bounded above by O(n2logn) and bounded below by (1 + e ) n for some e > 0. Chvatal 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2001
Accession Number
AD1021104

Entities

People

  • Gérard Cornuéjols
  • Yanjun Li

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Computer Programming
  • Contrast
  • Convex Sets
  • Equations
  • Inclusions
  • Inequalities
  • Intervals
  • Linear Programming
  • Literature
  • Mathematics
  • Schools
  • Standards
  • Theorems
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.