Skip to main content
SpringerLink
Log in

About Lagrangian Methods in Integer Optimization

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

It is well-known that the Lagrangian dual of an Integer Linear Program (ILP) provides the same bound as a continuous relaxation involving the convex hull of all the optimal solutions of the Lagrangian relaxation. It is less often realized that this equivalence is effective, in that basically all known algorithms for solving the Lagrangian dual either naturally compute an (approximate) optimal solution of the “convexified relaxation”, or can be modified to do so. After recalling these results we elaborate on the importance of the availability of primal information produced by the Lagrangian dual within both exact and approximate approaches to the original (ILP), using three optimization problems with different structure to illustrate some of the main points.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bacaud, L., C. Lemaréchal, A. Renaud, and C. Sagastizábal. (2001). “Bundle Methods in Stochastic Optimal Power Management: A Disaggregated Approach Using Preconditioners.” Computational Optimization and Applications 20, 227–244.

    Article  Google Scholar 

  • Bahiense, L., N. Maculan, and C. Sagastizábal. (2002). “The Volume Algorithm Revisited: Relation with Bundle Methods.” Math. Prog. 94(1), 41–70.

    Article  Google Scholar 

  • Balakrishnan, A., T.L. Magnanti, and R.T. Wong. (1989). “A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning.” Op. Res. 37, 716–740.

    Google Scholar 

  • Balakrishnan, A., T.L. Magnanti, and R.T. Wong. (1995). “A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design.” Op. Res. 43(1), 58–76.

    Google Scholar 

  • Barahona, F. and R. Anbil. (2000). “The Volume Algorithm: Producing Primal Solutions with a Subgradient Method.” Math. Prog. 87(3), 385–400.

    Article  Google Scholar 

  • Barnhart, C. and Y. Sheffi. (1993). “Dual-Ascent Methods for Large-Scale Multi-Commodity Flow Problems.” Naval Research Logistics 40, 305–324.

    Google Scholar 

  • Barnhart, C., C.A. Hane, and P. Vance. (1998). “Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems.” Op. Res. 32(3), 208–220.

    Google Scholar 

  • Benders, J.F. (1962). “Partitioning Procedures for Solving Mixed Variables Programming Problems.” Numerische Mathematik 4, 238–252.

    Article  Google Scholar 

  • Ben Amor, H. (2002). “Stabilisation de l'Algoritme de Génération de Colonnes.” Ph.D. Thesis. GERAD, Université de Montréal, Montreal, QC, Canada.

  • Borghetti, A., A. Frangioni, F. Lacalandra, and C.A. Nucci. (2002). “Lagrangian Heuristics Based on Disaggregated Bundle Methods for Hydrothermal Unit Commitment.” IEEE Transactions on Power Systems 18, 313–323.

    Article  Google Scholar 

  • Camerini, P.M., L. Fratta, and F. Maffioli. (1975). “On Improving Relaxation Methods by Modified Gradient Techniques.” Math. Prog. Study 3, 26–34.

    Google Scholar 

  • Cappanera, P., G. Gallo, and F. Maffioli. (2003). “Discrete Facility Location and Routing of Obnoxious Activities.” Disc. Appl. Math. 133, 3–28.

    Article  Google Scholar 

  • Castro, J. (2000). “A Specialized Interior-Point Algorithm for Multicommodity Network Flows.” SIAM J. on Opt. 10, 852–877.

    Article  Google Scholar 

  • Carraresi, P., L. Girardi, and M. Nonato. (1995). “Network Models, Lagrangian Relaxations and Subgradient Bundle Approach in Crew Scheduling Problems.” In J. Paixao (ed.), Computer Aided Scheduling of Public Transport, Lecture Notes in Economical and Mathematical Systems, Springer-Verlag.

  • Chang, S.-G. and B. Gavish. (1995). “Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems.” Op. Res. 43(1), 43–57.

    Google Scholar 

  • Crainic, T.G., A. Frangioni, and B. Gendron. (2001). “Bundle-Based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems.” Discrete Appl. Math. 112, 73– 99.

    Article  Google Scholar 

  • Dantzig, G.B. and P. Wolfe. (1960). “The Decomposition Principle for Linear Programs.” Op. Res. 8, 101–111.

    Google Scholar 

  • Dentcheva, D., A. Prékopa, and A. Ruszczynski. (2002). “Bounds for Integer Stochastic Programs with Probabilistic Constraints.” Discrete Appl. Math. 124, 55–65.

    Article  Google Scholar 

  • Deza, M.M. and M. Laurent. (1997). Geometry of Cuts and Metrics. Algorithms and Combinatorics 15, Springer-Verlag, Heidelberg.

    Google Scholar 

  • du Merle, O., J.-L. Goffin, and J.-P. Vial. (1998). “On Improvements to the Analytic Center Cutting Plane Method.” Computational Optimization and Applications 11, 37–52.

    Article  Google Scholar 

  • Farwolden, J.M. and W.B. Powell. (1994). “Subgradient Methods for the Service Network Design Problem.” Trans. Sci. 28(3), 256-272.

    Article  Google Scholar 

  • Frangioni, A. (1996). “Solving Semidefinite Quadratic Problems within Nonsmooth Optimization Algorithms.” Comput. & Oper. Res. 23, 1099–1118.

    Article  Google Scholar 

  • Frangioni, A. (2002). “Generalized Bundle Methods.” SIAM J. on Opt. 13(1), 117–156.

    Article  Google Scholar 

  • Frangioni, A. and G. Gallo. “A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min Cost Flow Problems.” INFORMS J. on Comp. 11(4), 370–393.

  • Frangioni, A., A. Lodi, and G. Rinaldi. (2005). “Lagrangian Approaches for Optimizing over the Semimetric Polytope.” Math. Prog. (to appear).

  • Fréville, A., M. Guignard, and S. Zhu. (1999). “Column generation and Lagrangean Relaxation: Two Powerful Related Tools for Integer Programming.” OPIM Department Report 99–12–22, The Wharton School, U. of Pennsylvania.

  • Fuduli, A. and M. Gaudioso. (2000). “Fixed and Virtual Stability Center Methods for Convex Nonsmooth Minimization.” In G. Di Pillo and F. Giannessi (eds.), Nonlinear Optimization and Applications 2, Kluwer Academic Publishers, pp. 105–122.

  • Gavish, B. (1985). “Augmented Lagrangian Based Algorithms for Centralized Network Design.” IEEE Trans. on Communications 33, 1247–1257.

    Article  Google Scholar 

  • Geoffrion, A.M. (1974). “Lagrangian Relaxation and its Uses in Integer Programming.” Math. Prog. Study 2, 82–114.

    Google Scholar 

  • Goffin, J.-L., J. Gondzio, R. Sarkissian, and J.-P. Vial. (1997). “Solving Nonlinear Multicommodity Flow Problems by the Analytic Center Cutting Plane Method.” Math. Prog. 76, 131–154.

    Article  Google Scholar 

  • Gouveia, L. (1995). “A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem.” Op. Res. 43, 130–141.

    Google Scholar 

  • Grigoriadis, M.D. and L.G. Kahchiyan. (1995). “An exponential-Function Reduction Method for Block-Angular Convex Programs.” Networks 26, 59–68.

    Google Scholar 

  • Guignard, M. and S. Kim. (1987). “Lagrangian Decomposition: A Model Yelding Stronger Lagrangian Bounds.” Math. Prog. 39, 215–228.

    Google Scholar 

  • Guignard, M. (1998). “Efficient Cuts in Lagrangean 'Relax-and-Cut' Schemes.” EJOR 105, 216–223.

    Article  Google Scholar 

  • Guignard, M. (2003). “Lagrangean Relaxation.” TOP 11(2), 151–228.

    Google Scholar 

  • Guignard, M. and M.B. Rosenwein. (1989). “An Application-Oriented Guide for Designing Lagrangian Dual Ascent Algorithms.” EJOR 43, 197–205.

    Google Scholar 

  • Held, M. and R. Carp. (1971). “The Travelling Salesman Problem and Minimum Spanning Trees: Part II.” Math. Prog. 1, 6–25.

    Article  Google Scholar 

  • Held, M., P. Wolfe, and H.P. Crowder. (1974). “Validation of Subgradient Optimization.” Math. Prog. 6, 62–88.

    Article  Google Scholar 

  • Hiriart-Urruty, J.-B. and C. Lemaréchal. (1993). Convex Analysis and Minimization Algorithms II—Advanced Theory and Bundle Methods. Grundlehren Math. Wiss. 306, New York: Springer-Verlag.

    Google Scholar 

  • Jones, K.L., I.J. Lustig, J.M. Farwolden, and W.B. Powell. (1993). “Multicommodity Network Flows: The Impact of Formulation on Decomposition.” Math. Prog. 62, 95–117.

    Article  Google Scholar 

  • Kiwiel, K. (1999). “A Bundle Bregman Proximal Method for Convex Nondifferentiable Optimization.” Math. Prog. 85, 241–258.

    Article  Google Scholar 

  • Kelley, J.E. (1960). “The Cutting-Plane Method for Solving Convex Programs.” Journal of the SIAM 8, 703–712.

    Google Scholar 

  • Larsson, T., M. Patriksson, and A.-B. Strömberg. (1999). “Ergodic, Primal Convergence in Dual Subgradient Schemes for Convex Programming.” Math. Prog. 86, 283–312.

    Article  Google Scholar 

  • Lemaréchal, C. (2001). Lagrangian Relaxation. In M. Jünger and D. Naddef (eds.), Computational Combinatorial Optimization, Springer Verlag, Heidelberg, pp. 115–160.

    Google Scholar 

  • Lemaréchal, C., A. Nemirovskii, and Y. Nesterov. (1995). “New variants of bundle methods.” Math. Prog. 69, 111–147.

    Article  Google Scholar 

  • Lemaréchal, C. and A. Renaud. (2001). “A Geometric Study of Duality Gaps, with Applications.” Math. Prog. 90, 399–427.

    Article  Google Scholar 

  • Lomonosov, M.V. (1985). “Combinatorial Approaches to Multiflow Problems.” Discrete Appl. Math. 11(1), 1–93.

    Article  Google Scholar 

  • McBride, R.D. (1998). “Advances in Solving the Multicommodity Flow Problem.” SIAM J. on Opt. 8, 947–955.

    Article  Google Scholar 

  • Nesterov, Y. (1995). “Complexity Estimates of Some Cutting Plane Methods Based on the Analytic Barrier.” Math. Prog. 69, 149–176.

    Google Scholar 

  • Padberg, M.W. and G. Rinaldi. (1991). “A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Travelling Salesman Problems.” SIAM Rev. 33, 60–100.

    Article  Google Scholar 

  • Pinar, M.C. and S.A. Zenios. (1994). “On Smoothing Exact Penalty Functions for Convex Constrained Optimization.” SIAM J. on Opt. 4, 486–511.

    Article  Google Scholar 

  • Poljak, B.T. (1977). “Subgradient Methods: A Survey of Soviet Research.” In C. Lemaréchal and R. Mifflin (eds.), Nonsmooth Optimization, IIASA Proceedings Series vol. 3, Pergamon Press.

  • Schultz, R. (2003). “Stochastic Programming with Integer Variables.” Math. Prog. 97, 285–309.

    Google Scholar 

  • Takriti, S. and J.R. Birge. (2000). “Lagrangean Solution Techniques and Bounds for Loosely Coupled Mixed Integer Stochastic Programs.” Op. Res. 48, 91–98.

    Article  Google Scholar 

  • Vazirani, V.V. (2001). Approximation Algorithms. New York: Springer-Verlag.

    Google Scholar 

  • Zhao, X. and P.B. Luh. (2002). “New Bundle Methods for Solving Lagrangian Relaxation Dual Problems.” JOTA 113(2), 373–397.

    Article  Google Scholar 

  • Zhuang, F. and F.D. Galiana. (1988). “Towards a More Rigorous and Practical Unit Commitment by Lagrangian Relaxation.” IEEE Transactions on Power Systems 3, 763–773.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127, Pisa, Italy

    Antonio Frangioni

Authors
  1. Antonio Frangioni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antonio Frangioni.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Frangioni, A. About Lagrangian Methods in Integer Optimization. Ann Oper Res 139, 163–193 (2005). https://doi.org/10.1007/s10479-005-3447-9

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-3447-9

Keywords

Search

Navigation