On the complexity of cutting-plane proofs
From MaRDI portal
Publication:580175
DOI10.1016/0166-218X(87)90039-4zbMATH Open0625.90056OpenAlexW2038193643MaRDI QIDQ580175FDOQ580175
Authors: Gy. 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
Recommendations
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Integer Programming with a Fixed Number of Variables
- Sensitivity theorems in integer linear programming
- Title not available (Why is that?)
- A Machine-Oriented Logic Based on the Resolution Principle
- Title not available (Why is that?)
- The relative efficiency of propositional proof systems
- The Specialization of Programs by Theorem Proving
- On Lovász' lattice reduction and the nearest lattice point problem
- Edmonds polytopes and a hierarchy of combinatorial problems
- On Cutting Planes
- The intractability of resolution
- Edmonds polytopes and weakly hamiltonian graphs
- Title not available (Why is that?)
- An observation on the structure of production sets with indivisibilities
- A Theorem Concerning the Integer Lattice
- Cutting planes in combinatorics
- Facet generating techniques
- Determining the Stability Number of a Graph
- Title not available (Why is that?)
- Propositional representation of arithmetic proofs (preliminary version)
- Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus
Cited In (75)
- Reflections on Proof Complexity and Counting Principles
- Resolution Width and Cutting Plane Rank Are Incomparable
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Cutting planes and the parameter cutwidth
- Cutting planes and the parameter cutwidth
- Lower bounds for cutting planes proofs with small coefficients
- On dedicated CDCL strategies for PB solvers
- Constrained pseudo-propositional logic
- A direct construction of polynomial-size OBDD proof of pigeon hole problem
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
- Title not available (Why is that?)
- On cutting-plane proofs in combinatorial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- On semantic cutting planes with very small coefficients
- Cutting-plane proofs in polynomial space
- Cutting plane and Frege proofs
- Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
- Restricted cutting plane proofs in Horn constraint systems
- Stabbing planes
- Title not available (Why is that?)
- On the rank of cutting-plane proof systems
- Rank bounds and integrality gaps for cutting planes procedures
- Polyhedral techniques in combinatorial optimization I: Theory
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization
- A connection between cutting plane theory and the geometry of numbers
- Cutting planes cannot approximate some integer programs
- How QBF expansion makes strategy extraction hard
- Monotone circuit lower bounds from resolution
- Structure of proofs and the complexity of cut elimination
- Testing satisfiability of CNF formulas by computing a stable set of points
- Resolution vs. cutting plane solution of inference problems: Some computational experience
- Several notes on the power of Gomory-Chvátal cuts
- Understanding cutting planes for QBFs
- On the complexity of cutting-plane proofs using split cuts
- Completeness of cutting planes revisited
- Reverse split rank
- Space Complexity in Polynomial Calculus
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- Upper bounds on complexity of Frege proofs with limited use of certain schemata
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- On the Chvátal rank of the pigeonhole principle
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- The complexity of recursive constraint satisfaction problems
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Cutting planes, connectivity, and threshold logic
- \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver
- Complexity of optimizing over the integers
- An exponential lower bound for the size of monotone real circuits
- Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search
- Narrow proofs may be maximally long
- Sensitivity theorems in integer linear programming
- The strength of multilinear proofs
- On meta complexity of propositional formulas and propositional proofs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
- Resolution proofs of generalized pigeonhole principles
- Input Proofs and Rank One Cutting Planes
- Title not available (Why is that?)
- Proving the infeasibility of Horn formulas through read-once resolution
- Depth lower bounds in Stabbing Planes for combinatorial principles
- Optimal length cutting plane refutations of integer programs
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Title not available (Why is that?)
- Cutting planes width and the complexity of graph isomorphism refutations
- Certified Core-Guided MaxSAT Solving
- Integer feasibility and refutations in UTVPI constraints using bit-scaling
- Achieving consistency with cutting planes
- QMaxSATpb: a certified MaxSAT solver
- Simplifying clausal satisfiability problems
- Certified dominance and symmetry breaking for combinatorial optimisation
This page was built for publication: On the complexity of cutting-plane proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580175)
