On cutting-plane proofs in combinatorial optimization
acyclic subdigraphbipartite subgraphcutting plane proofdepth of an inequalityknapsacklower boundsmaximum cutrank of a polyhedronset coveringset partitioningtravelling salesmanvalid inequalities
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polytopes and polyhedra (52Bxx) Linear programming (90C05) Boolean programming (90C09) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)
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.
- A class of facet producing graphs for vertex packing polyhedra
- A class of h-perfect graphs
- Chvátal closures for mixed integer programming problems
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- Computing low-capacity 0–1 knapsack polytopes
- Cutting planes from conditional bounds: A new approach to set covering
- Edmonds polytopes and a hierarchy of combinatorial problems
- Edmonds polytopes and weakly Hamiltonian graphs
- Faces for a linear inequality in O-1 variables
- Facet of regular O-1 polytopes
- Facets of the Bipartite Subgraph Polytope
- Facets of the knapsack polytope
- Facets of the Knapsack Polytope From Minimal Covers
- Flip-Flops in Hypohamiltonian Graphs
- Further facet generating procedures for vertex packing polytopes
- Graph Theory and Probability. II
- scientific article; zbMATH DE number 3870398 (Why is no real title available?)
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3699703 (Why is no real title available?)
- scientific article; zbMATH DE number 3495892 (Why is no real title available?)
- scientific article; zbMATH DE number 3561085 (Why is no real title available?)
- scientific article; zbMATH DE number 3609444 (Why is no real title available?)
- scientific article; zbMATH DE number 3619917 (Why is no real title available?)
- Matrices with the Edmonds-Johnson property
- On certain polytopes associated with graphs
- On circuits and subgraphs of chromatic graphs
- On Cutting Planes
- On stable set polyhedra for K//(1,3)free graphs
- On the 0,1 facets of the set covering polytope
- On the acyclic subgraph polytope
- On the best constants in the Khinchin inequality
- On the complexity of cutting-plane proofs
- On the cut polytope
- On the facial structure of set packing polyhedra
- On the facial structure of the set covering polytope
- On the maximum cardinality of a consistent set of arcs in a random tournament
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
- On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets
- On the structure of the monotone asymmetric travelling salesman polytope II: Hypotraceable facets
- On the symmetric travelling salesman problem I: inequalities
- On the symmetric travelling salesman problem II: lifting theorems and facets
- Optimal ranking of tournaments
- Optimally ranking unrankable tournaments
- Outline of an algorithm for integer solutions to linear programs
- Partial linear characterizations of the asymmetric travelling salesman polytope
- Polytope des independants d'un graphe série-parallèle
- Properties of vertex packing and independence system polyhedra
- Sensitivity theorems in integer linear programming
- Solution of a Large-Scale Traveling-Salesman Problem
- Subadditive lifting methods for partitioning and knapsack problems
- Technical Note—A Note on Zero-One Programming
- Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
- The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Two Results Concerning Multicoloring
- Cutting planes in combinatorics
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- The volume of relaxed Boolean-quadric and cut polytopes
- Theoretical challenges towards cutting-plane selection
- Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
- On semantic cutting planes with very small coefficients
- Aggregation-based cutting-planes for packing and covering integer programs
- A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set
- On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
- Cutting-plane proofs in polynomial space
- A connection between cutting plane theory and the geometry of numbers
- On the Chvátal rank of polytopes in the 0/1 cube
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Lattice closures of polyhedra
- Design and verify: a new scheme for generating cutting-planes
- On the rational polytopes with Chvátal rank 1
- Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
- On the complete set packing and set partitioning polytopes: properties and rank 1 facets
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- Several notes on the power of Gomory-Chvátal cuts
- Lower bounds on the size of general branch-and-bound trees
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization
- A lower bound on the Chvátal-rank of antiwebs
- On the Chvàtal-rank of antiwebs
- Rank of random half-integral polytopes. Extended abstract
- On the Chvàtal rank of linear relaxations of the stable set polytope
- Rank bounds and integrality gaps for cutting planes procedures
- A note on the Chvàtal-Rank of clique family inequalities
- Design and verify: A new scheme for generating cutting-planes
- On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
- scientific article; zbMATH DE number 4199652 (Why is no real title available?)
- scientific article; zbMATH DE number 4202024 (Why is no real title available?)
- On the rank of cutting-plane proof systems
- Technical Note—On Generating Cutting Planes from Combinatorial Disjunctions
- On the redundancy of cutting planes for linear complementarity problems
- scientific article; zbMATH DE number 49899 (Why is no real title available?)
- Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank
- On the Chvátal rank of certain inequalities
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Cutting planes cannot approximate some integer programs
- On the rank of mixed 0,1 polyhedra
- Clique problem, cutting plane proofs and communication complexity
- scientific article; zbMATH DE number 6829289 (Why is no real title available?)
- Transitive packing
- On the geometric rank of matching polytope
- Cutting planes from extended LP formulations
- A simple effective heuristic for embedded mixed-integer quadratic programming
- Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank
- On polytopes with linear rank with respect to generalizations of the split closure
- Complexity of optimizing over the integers
- Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube
- Random half-integral polytopes
- Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SPD operator
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Reducing the Chvátal rank through binarization
- On the power and limitations of branch and cut
- A lower bound for polynomial calculus with extension rule
- Optimizing over the subtour polytope of the travelling salesman problem
- The stable set polytope of quasi-line graphs
- On the complexity of cutting-plane proofs using split cuts
- Valid inequalities for mixed integer linear programs
This page was built for publication: On cutting-plane proofs in combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123134)