Cutting-plane proofs in polynomial space

DOI10.1007/BF01580849zbMath0735.90048OpenAlexW1990237439MaRDI QIDQ1813835

William Cook

Publication date: 25 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580849

zbMATH Keywords

system of linear inequalitiescutting plane proofrational coefficientsnon-existence of integral solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Theoretical challenges towards cutting-plane selection ⋮ Optimal length cutting plane refutations of integer programs ⋮ Design and Verify: A New Scheme for Generating Cutting-Planes ⋮ Design and verify: a new scheme for generating cutting-planes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of cutting-plane proofs
• Cutting planes in combinatorics
• The intractability of resolution
• On Lovász' lattice reduction and the nearest lattice point problem
• Geometric algorithms and combinatorial optimization.
• Edmonds polytopes and a hierarchy of combinatorial problems
• Facet Generating Techniques
• Integer Programming with a Fixed Number of Variables
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Solving Large-Scale Zero-One Linear Programming Problems
• Valid Linear Inequalities for Fixed Charge Problems
• Minkowski's Convex Body Theorem and Integer Programming
• On Cutting Planes
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Edmonds polytopes and weakly hamiltonian graphs