Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Gomory-chvatal cutting planes and the elementary closure of polyhedra
 
doctoral thesis

Gomory-chvatal cutting planes and the elementary closure of polyhedra

Eisenbrand, F.  
2000

The elementary closure P'; of a polyhedrom P is the intersection of P with all its Gomory-Chvátal cutting planes. P'; is a rational polyhedron provided that P is rational. The Chvátal-Gomory procedure is the iterative application of the elementary closure operation to P. The Chvátal rank is the minimal number of iterations needed to obtain P_I. It is always finite, but already in |R² one can construct polytopes of arbitrary large Chvátal rank. We show that the Chvátal rank of polytopes contained in the n-dimensional 0/1 cube is O(n² log n) and prove the lower bound (1+E) n, for some E> 0. We show that the separation problem for the elementary closure of a rational polyhedron is NP-hard. This solves a problem posed by Schrijver. Last we consider the elementary closure in fixed dimension. the known bounds for the number of inequalities defining P'; are exponential, even fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone from this polynomial description in fixed dimension with a maximal degree of violation in a natural sense.

  • Details
  • Metrics
Type
doctoral thesis
DOI
10.22028/D291-25909
Author(s)
Eisenbrand, F.  
Advisors
Bockmayr, Alexander
Date Issued

2000

Publisher

Universität des Saarlandes

EPFL units
DISOPT  
Available on Infoscience
May 29, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/26004
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés