On the complexity of cutting-plane proofs

DOI10.1016/0166-218X(87)90039-4zbMath0625.90056OpenAlexW2038193643MaRDI QIDQ580175

György Turán, William Cook, Collette R. Coullard

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90039-4

zbMATH Keywords

integral solution system of linear inequalities complexity of cutting-plane proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05)

Related Items

Narrow Proofs May Be Maximally Long, Discretely ordered modules as a first-order extension of the cutting planes proof system, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes, Cutting planes, connectivity, and threshold logic, On the complexity of finding shortest variable disjunction branch-and-bound proofs, On cutting-plane proofs in combinatorial optimization, Space Complexity in Polynomial Calculus, Simplifying clausal satisfiability problems, Unnamed Item, Reverse split rank, Integer feasibility and refutations in UTVPI constraints using bit-scaling, Depth lower bounds in Stabbing Planes for combinatorial principles, Complexity of optimizing over the integers, Achieving consistency with cutting planes, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Optimal length cutting plane refutations of integer programs, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, QMaxSATpb: a certified MaxSAT solver, The complexity of recursive constraint satisfaction problems, Cutting planes cannot approximate some integer programs, Unnamed Item, Sensitivity theorems in integer linear programming, Resolution proofs of generalized pigeonhole principles, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, Constrained pseudo-propositional logic, On meta complexity of propositional formulas and propositional proofs, ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES, Lower bounds for cutting planes proofs with small coefficients, Lower bounds for resolution and cutting plane proofs and monotone computations, On semantic cutting planes with very small coefficients, Cutting Planes and the Parameter Cutwidth, Cutting planes and the parameter cutwidth, On the complexity of cutting-plane proofs using split cuts, Upper bounds on complexity of Frege proofs with limited use of certain schemata, Testing satisfiability of CNF formulas by computing a stable set of points, Several notes on the power of Gomory-Chvátal cuts, Resolution Width and Cutting Plane Rank Are Incomparable, A direct construction of polynomial-size OBDD proof of pigeon hole problem, Unnamed Item, Understanding cutting planes for QBFs, Cutting-plane proofs in polynomial space, Polyhedral techniques in combinatorial optimization I: Theory, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II, On the Chvátal rank of the pigeonhole principle, Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search, \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver, Unnamed Item, An exponential lower bound for the size of monotone real circuits, Unnamed Item, Unnamed Item, On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations, How QBF expansion makes strategy extraction hard, Reflections on Proof Complexity and Counting Principles, On dedicated CDCL strategies for PB solvers

Cites Work