On the Chvátal rank of polytopes in the 0/1 cube (Q1961231): Difference between revisions

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\).