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. Journal articles
  4. On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures
 
Loading...
Thumbnail Image
research article

On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures

Averkov, Gennadiy
•
Conforti, Michele
•
Del Pia, Alberto
Show more
2013
Siam Journal On Discrete Mathematics

Given an integral polyhedron P subset of R-n and a rational polyhedron Q subset of R-n containing the same integer points as P, we investigate how many iterations of the Chvatal-Gomory closure operator have to be performed on Q to obtain a polyhedron contained in the affine hull of P. We show that if P contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on n. On the other hand, we prove that if P is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

  • Details
  • Metrics
Type
research article
DOI
10.1137/120898371
Web of Science ID

WOS:000325011800017

Author(s)
Averkov, Gennadiy
•
Conforti, Michele
•
Del Pia, Alberto
•
Di Summa, Marco  
•
Faenza, Yuri  
Date Issued

2013

Publisher

Siam Publications

Published in
Siam Journal On Discrete Mathematics
Volume

27

Issue

3

Start page

1492

End page

1502

Subjects

affine hull

•

Chvatal-Gomory closure

•

Chvatal rank

•

cutting plane

•

integral polyhedron

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
December 9, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/97560
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