On cutting-plane proofs in combinatorial optimization (Q1123134)

From MaRDI portal
Revision as of 08:26, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On cutting-plane proofs in combinatorial optimization
scientific article

    Statements

    On cutting-plane proofs in combinatorial optimization (English)
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    rank of a polyhedron
    0 references
    depth of an inequality
    0 references
    set covering
    0 references
    set partitioning
    0 references
    knapsack
    0 references
    bipartite subgraph
    0 references
    maximum cut
    0 references
    acyclic subdigraph
    0 references
    travelling salesman
    0 references
    cutting plane proof
    0 references
    valid inequalities
    0 references
    lower bounds
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references