Abstract
Branch-and-cut methods are among the more successful techniques for solving integer programming problems. They can also be used to prove that all solutions of an integer program satisfy a given linear inequality. We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We prove an exponential lower bound on the length of branch-and-cut proofs in the case where branching is on the variables and the cutting planes used are lift-and-project cuts (also called simple disjunctive cuts by some authors), Gomory-Chvátal cuts, and cuts arising from the N0 matrix-cut operator of Lovász and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential running time in the worst case.
This work was supported by ONR Grant N00014-98-1-0014.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ajtai, M.: The complexity of the pigeonhole principle. Combinatorica 14 (1994) 417–433
Alon, N., Boppana, R.: The monotone circuit complexity of Boolean functions. Combinatorica 7 (1987) 1–22
Andreev, A.E.: On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Mathematics-Doklady 31 (1985) 530–534
Balas, E.: Disjunctive programming. Annals of Discrete Mathematics 5 (1979) 3–51
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58 (1993) 295–324
Balas, E., Ceria, S., Cornuéjols, G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Science 42 (1996) 1229–1246
Balas, E., Ceria, S., Cornuéjols, G., Natraj, G.: Gomory cuts revisited. Operations Research Letters 19 (1996) 1–9
Beame, P., Pitassi, T.: Propositional proof complexity: past, present, and future. Bulletin of the European Association for Theoretical Computer Science 65 (1989) 66–89
Bonet, M., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic 62 (1997) 708–728.
Boppana, R., Sipser, M.: The complexity of finite functions. In: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. MIT Press/Elsevier (1990) 757–804
Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics 4 (1973) 305–337
Chvátal, V.: Hard knapsack problems. Operations Research 28 (1980) 1402–1411
Chvátal, V.: Cutting-plane proofs and the stability number of a graph. Report Number 84326-OR. Insitut für Ökonometrie und Operations Research, Universität Bonn, Bonn. (1984)
Chvátal, V.: Cutting planes in combinatorics. European Journal of Combinatorics 6 (1985) 217–226
Chvátal, V., Cook, W., Hartmann, M.: On cutting plane proofs in combinatorial optimization. Linear Algebra and its Applications 114/115 (1989) 455–499
Chvátal, V., Szemerédi, E.: Many hard examples for resolution. Journal of the Association for Computing Machinery 35 (1988) 759–768
Cook, S.A., Haken, A.: An exponential lower bound for the size of monotone real circuits. Journal of Computer and System Sciences 58 (1999) 326–335
Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44 (1979) 36–50
Cook, W.: Cutting-plane proofs in polynomial space. Mathematical Programming 47 (1990) 11–18
Cook, W., Coullard, C.R., Turán, Gy.: On the complexity of cutting-plane proofs. Discrete Applied Mathematics 18 (1987) 25–38
Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)
Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Mathematics of Operations Research 26 (2001) 19–30
Cook, W., Hartmann, M.: On the complexity of branch and cut methods for the traveling salesman problem. In: Seymour, P.D., Cook, W. (eds.): Polyhedral Combinatorics, Vol. 1, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1990) 75–82
G. Cornuéjols and Li, Y.: Elementary closures for integer programs. Operations Research Letters 28 (2001) 1–8
Dash, S.: On the matrix cuts of Lovász and Schrijver and their use in integer programming. Ph.D. Thesis. Rice University, Houston, Texas (2001). Available as: Technical Report TR01-08. Rice University (2001)
Eisenbrand, F., Schulz, A.S.: Bounds on the Chvátal rank of polytopes in the 0/1-cube. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.): Integer Programming and Combinatorial Optimization, 7th International IPCO Conference. Springer, Berlin (1999) 137–150
Goemans, M.X., Tunçel, L.: When does the positive semidefiniteness constraint help in lifting procedures. Mathematics of Operations Research 26 (2001) 796–815
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64 (1958) 275–278
Gomory, R.E.: An algorithm for the mixed integer problem. RM-2597, The Rand Corporation (1960)
Grötschel, M., Pulleyblank, W.R.: Clique tree inequalities and the symmetric traveling salesman problem. Mathematics of Operations Research 11 (1986) 1–33
Haken, A.: The intractability of resolution. Theoretical Computer Science 39 (1985) 297–308
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press (1985)
Jeroslow, R.G.: Trivial integer programs unsolvable by branch-and-bound. Mathematical Programming 6 (1974) 105–109
Jeroslow, R.G.: A cutting-plane game for facial disjunctive programs. SIAM Journal on Control and Optimization 18 (1980) 264–281
Krajíček, J.: Lower bounds to the size of constant-depth propositional proofs. Journal of Symbolic Logic 59 (1994) 73–86
Krajíček, J.: Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. Journal of Symbolic Logic 62 (1997) 457–486
Lovász, L.: Stable sets and polynomials. Discrete Mathematics 124 (1994) 137–153
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1 (1991) 166–190
Pudlák, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. Journal of Symbolic Logic 62 (1997) 981–998
Pudlák, P.: On the complexity of propositional calculus. In: Sets and Proofs, Invited papers from Logic Colloquium 1997. Cambridge University Press (1999) 197–218
Razborov, A.A., Lower bounds for the monotone complexity of some boolean functions. Dokladi Akademii Nauk SSSR 281 (1985) 798–801 (in Russian). English translation in: Soviet Mathematics-Doklady 31 (1985) 354–357
Razborov, A.A., Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic. Izvestiiya of the RAN 59 (1995) 201–224
Schrijver, A.: On cutting planes. In: Deza, M., Rosenberg, I.G. (eds.): Combinatorics 79 Part II, Annals of Discrete Mathematics 9. North Holland, Amsterdam (1980) 291–296
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3 (1990) 411–430
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dash, S. (2002). An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs. In: Cook, W.J., Schulz, A.S. (eds) Integer Programming and Combinatorial Optimization. IPCO 2002. Lecture Notes in Computer Science, vol 2337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47867-1_11
Download citation
DOI: https://doi.org/10.1007/3-540-47867-1_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43676-8
Online ISBN: 978-3-540-47867-6
eBook Packages: Springer Book Archive