In order to prove that a system of linear inequalities \(a^ T_ ix\leq b_ i\), \(1\leq i\leq m\), has no integral solution, for \(i=1,\ldots,M\) one may recursively derive a linear inequality \(a^ T_{m+i}x\leq b_{m+i}\), by nonnegative linear combination of previously known linear inequalities and integer roundown of the resulting righthandside. Then, if the last inequality is of the form \(0^ Tx\leq-1\), infeasibility is obvious. Such a system of \(m+M\) inequalities is called a cutting plane proof of length \(M\). The existence of cutting plane proofs for systems with rational coefficients is well-known. Here, for such systems, the existence of a cutting plane proof of length \(O(n^{3n})\) is shown, which can be carried out in polynomial workspace.
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Cutting planes in combinatorics
- Edmonds polytopes and a hierarchy of combinatorial problems
- Edmonds polytopes and weakly hamiltonian graphs
- Facet generating techniques
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 4006346 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3373541 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- On Cutting Planes
- On Lovász' lattice reduction and the nearest lattice point problem
- On the complexity of cutting-plane proofs
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Solving Large-Scale Zero-One Linear Programming Problems
- The intractability of resolution
- Valid Linear Inequalities for Fixed Charge Problems
- On cutting-plane proofs in combinatorial optimization
- Theoretical challenges towards cutting-plane selection
- On semantic cutting planes with very small coefficients
- Design and verify: a new scheme for generating cutting-planes
- Several notes on the power of Gomory-Chvátal cuts
- scientific article; zbMATH DE number 6387509 (Why is no real title available?)
- Design and verify: A new scheme for generating cutting-planes
- On hardly linearly provable systems
- On the rank of cutting-plane proof systems
- scientific article; zbMATH DE number 4024785 (Why is no real title available?)
- Input Proofs and Rank One Cutting Planes
- Polynomially and superexponentially shorter proofs in fragments of arithmetic
- scientific article; zbMATH DE number 1263234 (Why is no real title available?)
- scientific article; zbMATH DE number 515726 (Why is no real title available?)
- Lower bounds for cutting planes proofs with small coefficients
- Cutting planes cannot approximate some integer programs
- scientific article; zbMATH DE number 6829289 (Why is no real title available?)
- Stabbing planes
- Completeness of cutting planes revisited
- On the complexity of cutting-plane proofs
- Optimal length cutting plane refutations of integer programs
- Optimal length cutting plane refutations of integer programs
- On the complexity of cutting-plane proofs using split cuts
This page was built for publication: Cutting-plane proofs in polynomial space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813835)
