On cutting-plane proofs in combinatorial optimization (Q1123134)

Consider a polyhedron \(P\) in the \(n\)-dimensional Euclidean space \({\mathbb R}^ n\). Let \({\mathbb Z}^ n\) denote the set of vectors in \({\mathbb R}^ n\) all of whose components are integers, and let \(P'=\{x\in P: a^ Tx\leq b\) whenever \(a\in {\mathbb Z}^ n\), \(b\in {\mathbb Z}\) and \(\max \{a^ Tx: x\in P\}<b+1\}\). Obviously, \(P\cap {\mathbb Z}^ n\subset P'\). Moreover, if \(P^ 0=P\) and, recursively, \(P^ j=(P^{(j-1)})'\) for all \(j\in {\mathbb N}\), then \(P\cap {\mathbb Z}^ n\subset P^{(j)}\) for all \(j\in {\mathbb Z}_+\). If \(P_ I\) denotes the convex hull of \(P\cap {\mathbb Z}^ n\), then \(P_ I\subset P^{(j)}\) for all \(j\in {\mathbb Z}_+.\) The rank of a polyhedron \(P\) is the smallest \(j\) such that \(P^{(j)}=P_ I\). The depth of an inequality \(a^ Tx\leq b\) relative to \(P\) is the smallest \(d\) such that \(a^ Tx\leq b\) is valid over \(P^{(d)}\). By exhibiting an inequality valid over \(P\cap {\mathbb Z}^ n\) and establishing a lower bound on its depth, this paper provides lower bounds on the rank of polyhedra featured in popular formulations of the stable set, set covering, set partitioning, knapsack, bipartite subgraph, maximum cut, acyclic subdigraph, asymmetric and symmetric travelling salesman problem. The relationship between the rank of polyhedra and ``cutting plane proofs'' is explained: let \(m\) and \(M\) be positive integers and let \[ (1)\quad a^ T_ ix\leq b_ i\;\text{for}\;i=1,...,m\;\text{and}\;(2)\quad a^ T_ ix\leq b_ i\;\text{for}\;i=m+1,...,m+M \] be sequences of linear inequalities in \(n\) variables such that \(a_ i\in {\mathbb Z}^ n\) whenever \(m<i\leq m+M\). Finally, let (3) \(w_{ik}\) for \(m<i\leq m+M\), \(1\leq k<i\) be nonnegative integers such that \(a_ i=\sum (w_{ik}a_ k: k=1,...,i-1)\) and \(b_ i\geq \lfloor \sum (w_{ik}b_ k: k=1,...,i-1)\rfloor\) for all \(i\). The sequence (2) along with the numbers (3) is called a cutting plane proof of \(a^ T_{m+M}x\leq b_{m+M}\) from (1), and \(M\) is called its length. Lower bounds on the depth of particular valid inequalities over (partial) linear descriptions associated with some of the above mentioned problems are presented together with lower bounds on corresponding cutting plane proofs. Finally, some of the lower bounds on depth are shown to be best possible within a constant factor.