Abstract
Following Chvátal, cutting planes may be viewed as a proof system for establishing that a given system of linear inequalities has no integral solution. We show that such proofs may be carried out in polynomial workspace.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L. Babai, “On Lovász' lattice recudtion nad the nearest lattice point problem,”Combinatorica 6 (1986) 1–13.
S.C. Boyd and W.R. Pulleyblank, “Facet generating techniques,” in preparation.
V. Chvátal, “Edmonds polytopes and a hierarchy of combinatorial problems,”Discrete Mathematics 4 (1973) 305–337.
V. Chvátal, “Edmonds polytopes and weakly hamiltonian graphs,”Mathematical Programming 5 (1973) 29–40.
V. Chvátal, “Cutting-plane proofs and the stability number of a graph,” Report Number 84326-OR, Institut für Ökonometrie und Operations Research, Universität Bonn (Bonn, 1984).
V. Chvátal, “Cutting planes in combinatorics,”European Journal of Combinatorics 6 (1986) 217–226.
W. Cook, C.R. Coullard and Gy. Turán, “On the complexity of cutting-plane proofs,”Discrete Applied Mathematics 18 (1987) 25–38.
C.R. Coullard, personal communication.
H. Crowder, E.L. Johnson and M.W. Padberg, “Solving large scale zero-one linear programming problems,”Operations Research 31 (1983) 803–834.
H.P. Crowder and M.W. Padberg, “Solving large scale symmetric travelling salesman problems to optimality,”Management Science 26 (1980) 495–509.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “Solution of a large-scale traveling salesman problem,”Operations Research 2 (1954) 393–410.
R.E. Gomory, “An algorithm for integer solutions to linear programs,” in: R.L. Graves and P. Wolfe, eds.,Recent Advances in Mathematical Programming (McGraw-Hill, New York, 1963) pp. 269–302.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem,”Operations Research 32 (1984) 1195–1220.
M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms in Combinatorial Optimization (Springer, Heidelberg, 1987).
A. Haken, “The intractability of resolution,”Theoretical Computer Science 39 (1985) 297–308.
R. Kannan, “Minkowski's convex body theorem and integer programming,”Mathematics of Operations Research 12 (1987) 415–440.
R. Kannan and L. Lovász, “Covering minima and lattice point free convex bodies,” Report Number 86427-OR, Institut für Ökonometrie und Operations Research, Universität Bonn (Bonn, 1986).
D. Kozen, “Lower bounds for natural proof systems,”Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (1977) 252–266.
D. Kozen, “Pebblings, edgings, and equational logic,”Proceedings of the 16th ACM Symposium on the Theory of Computing (1984) 428–435.
H.W. Lenstra, “Integer programming with a fixed number of variables,”Mathematics of Operations Research (1983) 538–548.
M.W. Padberg, T.J. van Roy and L.A. Wolsey, “Valid linear inequalities for fixed charge problems,”Operations Research 33 (1985) 842–861.
A. Schrijver, “On cutting planes,”Annals of Discrete Mathematics 9 (1980) 291–296.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, 1986).
Author information
Authors and Affiliations
Additional information
Research supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, FR Germany and by NSF grant ECS-8611841.
Rights and permissions
About this article
Cite this article
Cook, W. Cutting-plane proofs in polynomial space. Mathematical Programming 47, 11–18 (1990). https://doi.org/10.1007/BF01580849
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580849