On the complexity of cutting-plane proofs using split cuts

DOI10.1016/j.orl.2009.10.010zbMath1187.90204OpenAlexW2009866245MaRDI QIDQ969513

Sanjeeb Dash

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

zbMATH Keywords

split cutmixed-integer roundingcutting-plane proofmonotone interpolation

Mathematics Subject Classification ID

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