On the complexity of cutting-plane proofs using split cuts
From MaRDI portal
Publication:969513
DOI10.1016/j.orl.2009.10.010zbMath1187.90204OpenAlexW2009866245MaRDI QIDQ969513
Publication date: 7 May 2010
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2009.10.010
Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (7)
Computational Experiments with Cross and Crooked Cross Cuts ⋮ Complexity of optimizing over the integers ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Cutting planes cannot approximate some integer programs ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of cutting-plane proofs
- MIR closures of polyhedral sets
- Chvátal closures for mixed integer programming problems
- The monotone circuit complexity of Boolean functions
- An exponential lower bound for the size of monotone real circuits
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Sequential pairing of mixed integer inequalities
- Several notes on the power of Gomory-Chvátal cuts
- Edmonds polytopes and a hierarchy of combinatorial problems
- Valid inequalities based on simple mixed-integer sets
- On the Matrix-Cut Rank of Polyhedra
- Outline of an algorithm for integer solutions to linear programs
- Aggregation and Mixed Integer Rounding to Solve MIPs
- Lower bounds to the size of constant-depth propositional proofs
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
This page was built for publication: On the complexity of cutting-plane proofs using split cuts
