On the complexity of cutting-plane proofs

DOI10.1016/0166-218X(87)90039-4MaRDI QIDQ580175zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

system of linear inequalitiesintegral solutioncomplexity of cutting-plane proofs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 512977
• Cutting plane and Frege proofs
• Cutting-plane proofs in polynomial space
• On the rank of cutting-plane proof systems
• scientific article; zbMATH DE number 6829289

Cites work

• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 3626917 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• A Machine-Oriented Logic Based on the Resolution Principle
• A Theorem Concerning the Integer Lattice
• An observation on the structure of production sets with indivisibilities
• Cutting planes in combinatorics
• Determining the Stability Number of a Graph
• Edmonds polytopes and a hierarchy of combinatorial problems
• Edmonds polytopes and weakly hamiltonian graphs
• Facet generating techniques
• Integer Programming with a Fixed Number of Variables
• On Cutting Planes
• On Lovász' lattice reduction and the nearest lattice point problem
• Propositional representation of arithmetic proofs (preliminary version)
• Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus
• Sensitivity theorems in integer linear programming
• The Specialization of Programs by Theorem Proving
• The intractability of resolution
• The relative efficiency of propositional proof systems

Cited in

(75)

• Lower bounds for resolution and cutting plane proofs and monotone computations
• On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
• Cutting-plane proofs in polynomial space
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• Cutting planes, connectivity, and threshold logic
• Testing satisfiability of CNF formulas by computing a stable set of points
• Sensitivity theorems in integer linear programming
• Reflections on Proof Complexity and Counting Principles
• scientific article; zbMATH DE number 6829289 (Why is no real title available?)
• scientific article; zbMATH DE number 1263234 (Why is no real title available?)
• Upper bounds on complexity of Frege proofs with limited use of certain schemata
• On dedicated CDCL strategies for PB solvers
• Resolution proofs of generalized pigeonhole principles
• A direct construction of polynomial-size OBDD proof of pigeon hole problem
• On the rank of cutting-plane proof systems
• On cutting-plane proofs in combinatorial optimization
• scientific article; zbMATH DE number 408793 (Why is no real title available?)
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Rank bounds and integrality gaps for cutting planes procedures
• Input Proofs and Rank One Cutting Planes
• Constrained pseudo-propositional logic
• An exponential lower bound for the size of monotone real circuits
• Polyhedral techniques in combinatorial optimization I: Theory
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Restricted cutting plane proofs in Horn constraint systems
• Monotone circuit lower bounds from resolution
• Resolution vs. cutting plane solution of inference problems: Some computational experience
• Resolution Width and Cutting Plane Rank Are Incomparable
• On the complexity of cutting-plane proofs using split cuts
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• Reverse split rank
• Cutting plane and Frege proofs
• Structure of proofs and the complexity of cut elimination
• Complexity of optimizing over the integers
• Lower bounds for cutting planes proofs with small coefficients
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Several notes on the power of Gomory-Chvátal cuts
• The strength of multilinear proofs
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver
• Stabbing planes
• Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search
• Cutting planes and the parameter cutwidth
• scientific article; zbMATH DE number 7178366 (Why is no real title available?)
• Narrow proofs may be maximally long
• Cutting planes and the parameter cutwidth
• On the Chvátal rank of the pigeonhole principle
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization
• Space Complexity in Polynomial Calculus
• On meta complexity of propositional formulas and propositional proofs
• A connection between cutting plane theory and the geometry of numbers
• Cutting planes cannot approximate some integer programs
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• Understanding cutting planes for QBFs
• On semantic cutting planes with very small coefficients
• scientific article; zbMATH DE number 515726 (Why is no real title available?)
• How QBF expansion makes strategy extraction hard
• The complexity of recursive constraint satisfaction problems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• On the complexity of finding shortest variable disjunction branch-and-bound proofs
• Completeness of cutting planes revisited
• Certified dominance and symmetry breaking for combinatorial optimisation
• Proving the infeasibility of Horn formulas through read-once resolution
• Integer feasibility and refutations in UTVPI constraints using bit-scaling
• Achieving consistency with cutting planes
• Certified Core-Guided MaxSAT Solving
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Cutting planes width and the complexity of graph isomorphism refutations
• Depth lower bounds in Stabbing Planes for combinatorial principles
• scientific article; zbMATH DE number 7455719 (Why is no real title available?)
• Optimal length cutting plane refutations of integer programs
• QMaxSATpb: a certified MaxSAT solver
• Simplifying clausal satisfiability problems

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)