On the complexity of cutting-plane proofs using split cuts

DOI10.1016/j.orl.2009.10.010zbMath1187.90204MaRDI 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 cut; mixed-integer rounding; cutting-plane proof; monotone interpolation

Mathematics Subject Classification ID

90C10: Integer programming

90C11: Mixed integer programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C60: Abstract computational complexity for mathematical programming problems

Related Items

Relaxations of mixed integer sets from lattice-free polyhedra, Cutting planes cannot approximate some integer programs, Computational Experiments with Cross and Crooked Cross Cuts

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