Abstract
Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation with various decomposition methods to yield further improvement in computed bounds. In this paper, we describe a framework within which most of these methods can be viewed from a common theoretical perspective. We then discuss how the framework can be extended to obtain a decomposition-based separation technique we call decompose and cut. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such as those to a given relaxation, can frequently be separated much more easily than arbitrary real vectors.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal, K., van Hoesel, S.: Polyhedral techniques in combinatorial optimization. Statistica Neerlandica 50, 3–26 (1996)
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: TSP cuts which do not conform to the template paradigm. In: Computational Combinatorial Optimization, Springer, 2001 pp. 261–303
Augerat, P., Belenguer, J.M., Benavent, E., Corberán, A., Naddef, D., Rinaldi, G.: Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem. Technical Report 949-M, Université Joseph Fourier, Grenoble, France, 1995
Balas, E., Christofides, N.: A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming 21, 19–46 (1981)
Balas, E., Qi, L.: Linear-time separation algorithms for the three-index assignment polytope. Discrete Applied Mathematics 43, 1–12 (1993)
Balas, E., Saltzman, M.J.: Facets of the three-index assignment polytope. Discrete Applied Mathematics 23, 201–229 (1989)
Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Operations Research 39, 150–161 (1991)
Barahona, F., Anbil, R.: The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming 87, 385–399 (2000)
Barahona, F., Jensen, D.: Plant location with minimum inventory. Mathematical Programming 83, 101–111 (1998)
Barnhart, C., Hane, C.A., Vance, P.H.: Using branch-and-price-and-cut to solve origin-destination integer multi-commodity flow problems. Operations Research 48, 318–326 (2000)
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H.: Branch and price: Column generation for solving huge integer programs. Operations Research 46, 316–329 (1998)
Beasley, J.E.: A SST-based algorithm for the steiner problem in graphs. Networks 19, 1–16 (1989)
Beasley, J.E.: Lagrangean relaxation. In: C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Optimization. Wiley, 1993
Belloni, A., Lucena, A.: A Lagrangian heuristic for the linear ordering problem. In: M.G.C. Resende, J. Pinho de Sousa (eds.), Metaheuristics: Computer Decision-Making. Kluwer Academic, 2003, pp. 123–151
Calheiros, F.C., Lucena, A., de Souza, C.: Optimal rectangular partitions. Networks 41, 51–67 (2003)
Caprara, A., Fischetti, M., Toth, P.: Algorithms for the set covering problem. Annals of Operations Research 98, 353–371 (2000)
Carraresi, P., Frangioni, A., Nonato, M.: Applying bundle methods to optimization of polyhedral functions: An applications-oriented development. Technical Report TR-96-17, Universitá di Pisa, 1996
Dantzig, G., Wolfe, P.: Decomposition principle for linear programs. Operations Research 8, 101–111 (1960)
Danzig, G.B., Ramser, R.H.: The truck dispatching problem. Management Science 6, 80–91 (1959)
Poggi de Aragsao, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. Working paper, Pontifíca Universidade Católica do Rio de Janeiro, 2004. Available from http://www.inf.puc-rio.br/˜uchoa/doc/rbcp-a.pdf
Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Management Science 27, 1–18 (1981)
Fisher, M.L.: Optimal solution of vehicle routing problems using minimum k-trees. Operations Research 42, 626–642 (1994)
Fukasawa, R., Poggi de Aragão, M., Reis, M., Uchoa, E.: Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem. In: Proceedings of the International Network Optimization Conference. Evry, France, 2003, pp. 231–236
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979
Geoffrion, A.: Lagrangian relaxation for integer programming. Mathematical Programming Study 2, 82–114 (1974)
Goemans, M.X.: The steiner tree polytope and related polyhedra. Mathematical Programming 63, 157–182 (1994)
Goffin, J.L., Vial, J.P.: Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Technical Report 99.02, Logilab, Geneva, Switzerland, 1999
Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Technical report, University of Geneva, Logilab, HEC Geneva, 1996
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)
Guignard, M.: Efficient cuts in Lagrangean ``relax-and-cut'' schemes. European Journal of Operational Research 105, 216–223 (1998)
Guignard, M.: Lagrangean relaxation. Top 11, 151–228 (2003)
Huisman, D., Jans, R., Peeters, M., Wagelmans, A.: Combining column generation and Lagrangian relaxation. Technical report, Erasmus Research Institute of Management, Rotterdamn, The Netherlands, 2003
Hunting, M., Faigle, U., Kern, W.: A Lagrangian relaxation approach to the edge-weighted clique problem. European Journal of Operational Research 131, 119–131 (2001)
Kohl, N., Desrosiers, J., Madsen, O.B.G., Solomon, M.M., Soumis, F.: 2-path cuts for the vehicle routing problem with time windows. Transportation Science 33, 101–116 (1999)
Kopman, L.: A New Generic Separation Routine and Its Application In a Branch and Cut Algorithm for the Capacitated Vehicle Routing Problem. PhD thesis, Cornell University, May 1999
Laporte, G., Nobert, Y., Desrouchers, M.: Optimal routing with capacity and distance restrictions. Operations Research 33, 1050–1073 (1985)
Linderoth, J., Galati, M.: Knapsack constrained circuit problem. Unpublished working paper, 2004
Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Technical Report 008-2004, Technische Universität Berlin, 2004
Lucena, A.: Tight bounds for the steiner problem in graphs. Talk given at TIMS-XXX-SOBRAPO XXIII Joint International Meeting, Rio de Janeiro, July 1991
Lucena, A.: Steiner problem in graphs: Lagrangean relaxation and cutting planes. COAL Bulletin 28, 2–8 (1992)
Lucena, A.: Non-delayed relax-and-cut algorithms. Working paper, Departmaneto de Administração, Universidade Federal do Rio de Janeiro, 2004
Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming 100, 423–445 (2004)
Margot, F., Prodon, A., Liebling, T.M.: Tree polyhedron on 2-tree. Mathematical Programming 63, 183–192 (1994)
Richard Martin, K.: Large Scale Linear and Integer Optimization - A Unified Approach. Kluwer, Boston, MA, 1999
Martinhon, C., Lucena, A., Maculan, N.: Stronger k-tree relaxations for the vehicle routing problem. European Journal of Operational Research 158, 56–71 (2004)
Miller, D.: A matching based exact algorithm for capacitated vehicle routing problems. ORSA Journal on Computing 7, 1–9 (1995)
Müller-Hannemann, M., Schwartz, A.: Implementing weighted b-matching algorithms: Towards a flexible software design. In: Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX99). Vol. 1619 of Lecture notes in computer science. Springer-Verlag, Baltimore, MD, 1999, pp. 18–36
Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: P. Toth, D. Vigo (eds.), The Vehicle Routing Problem. SIAM, 2002, pp. 53–84
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, Inc., USA, 1st edition, 1988
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York, 1988
Parker, R.G., Rardin, R.L.: Discrete Optimization. Academic Press, Inc., 1988
Pigatti, A.: Modelos e algoritmos para o problema de aloção generalizada e aplicações. PhD thesis, Pontifícia Universidade Católica do Rio de Janeiro, 2003
Prim, R.: Shortest connection networks and some generalizations. Bell System Technical Journal. 36, 1389–1401 (1957)
Ralphs, T.K.: Parallel Branch and Cut for Vehicle Routing. PhD thesis, Cornell University, May 1995
Ralphs, T.K., Galati, M.V.: Decomposition in integer programming. In: J. Karlof (ed), Integer Programming: Theory and Practice. CRC Press, 2005. To appear
Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E., Jr: On the capacitated vehicle routing problem. Mathematical Programming 94, 343–359 (2003)
Rousseau, L.M., Gendreau, M., Feillet, D.: Interior point stabilization for column generation. Working paper, Cahier du Gerad, 2003. Available from http://www.lia.univ-avignon.fr/fich_art/380-IPS.pdf
Chvátal, V.: Linear Programming. W.H. Freeman and Company, 1983
van den Akker, J.M., Hurkens, C.A.J., Savelsbergh, M.W.P.: Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing 12, 111–124 (2000)
Vanderbeck, F.: Lot-sizing with start-up times. Management Science 44, 1409–1425 (1998)
Vanderbeck, F.: A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Working paper, 2003. Available from http://www.math.u-bordeaux.fr/~fv/papers/dwcPap.pdf
Wei, G., Yu, G.: An improved O(n 2 log n) algorithm for the degree-constrained minimum k-tree problem. Technical report, The University of Texas at Austin, Center for Management of Operations and Logistics, 1995
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ralphs, T., Galati, M. Decomposition and Dynamic Cut Generation in Integer Linear Programming. Math. Program. 106, 261–285 (2006). https://doi.org/10.1007/s10107-005-0606-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0606-3