On the Chvátal rank of polytopes in the 0/1 cube
type: Item
instance of: scholarly article
title: On the Chvátal rank of polytopes in the 0/1 cube
zbMATH Open document ID: 0956.52013
DOI: 10.1016/S0166-218X(99)00156-0
author: Alexander Bockmayr
author: Friedrich Eisenbrand
author: Andreas S. Schulz
author: Mark Hartmann
published in: Discrete Applied Mathematics
publication date: 2001-03-04T00:00:00Z
review text: Let \(P=\{ x\in\mathbb R^n |Ax\leq b\}\) be a polyhedron (here \(A\in\mathbb R^{m\times n}\) and \(b\in\mathbb R^m\)). An inequality \(c^Tx\leq\lfloor\delta\rfloor\), with \(c\in \mathbb Z^n\) and \(\delta=\max\{ c^Tx |x\in P\}\), is called a Chvátal-Gomory cutting plane (here \(\lfloor\delta\rfloor\) denotes the greatest integer less than or equal to \(\delta\)). The set of vectors \(P'\) satisfying all cutting planes for \(P\) is called the elementary closure of \(P\). Let \(P^{(0)}=P\) and \(P^{(i+1)}=(P^{(i)})'\), for \(i\geq 0\). Then the Chvátal rank of \(P\) is the smallest number \(t\) such that \(P^{(t)}=P_I\), where \(P_I\) is the integer hull of \(P\), i.e., the convex hull of \(P\cap\mathbb Z^n\). The main result is as follows: the Chvátal rank of any polytope \(P\subset [0,1]^n\) in the n-dimensional 0/1 cube is at most \((\lfloor n/2\log_2 n\rfloor +1)n^2\). The authors prove also the linear upper and lower bound \(n\) for the case \(P\cap\mathbb Z^n=\emptyset\).
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1389496
zbMATH Keywords: rational polyhedron
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: integral polytope
zbMATH Keywords: Chvàtal-Gomory rounding procedure
zbMATH Keywords: complexity of the integer hull
reviewed by: Victor Alexandrov
MaRDI profile type: Publication
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: On cutting-plane proofs in combinatorial optimization
cites work: Sensitivity theorems in integer linear programming
cites work: Q3351148
cites work: Q3351144
cites work: Q4040221
cites work: On Cutting Planes
cites work: Q3818127
Recommended article: Q4263708
Recommended article: Bounds on the Chvatal rank of polytopes in the 0/1-cube
Recommended article: Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
Recommended article: On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
Recommended article: On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank
Recommended article: On the rational polytopes with Chvátal rank 1
Recommended article: 0/1 Polytopes with Quadratic Chvátal Rank
Recommended article: Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank
Recommended article: Q4537736
description: scientific article; zbMATH DE number 1389496