Abstract
Lagrangian relaxation is usually considered in the combinatorial optimization community as a mere technique, sometimes useful to compute bounds. It is actually a very general method, inevitable as soon as one bounds optimal values, relaxes constraints, convexifies sets, generates columns, etc. In this paper we review this method, from both points of view of theory (to dualize a given problem) and algorithms (to solve the dual by nonsmooth optimization).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alizadeh, F. (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5(1), 13–51.
Anstreicher, K., & Wolsey, L. A. (1993, in press). On dual solutions in subgradient optimization, Unpublished manuscript, CORE, Louvain-la-Neuve, Belgium. Mathematical Programming.
Babonneau, F., & Vial, J. P. (2007, in press). Vial, Accpm with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. Mathematical Programming.
Barahona, F., & Anbil, R. (2000). The volume algorithm: producing primal solutions with a subgradient method. Mathematical Programming, 87(3), 385–399.
Bertsekas, D. P. (1995). Nonlinear programming. Athena Scientific.
Bertsekas, D. P., Lauer, G. S., Sandell, N. R., & Posberg, T. A. (1983). Optimal short-term scheduling of large-scale power systems. IEEE Transactions on Automatic Control, 28, 1–11.
Briant, O., Lemaréchal, C., Meurdesoif, P., Michel, S., Perrot, N., & Vanderbeck, F. (2005, in press). Comparison of bundle and classical column generation. RR 5453, INRIA. http://www.inria.fr/rrrt/rr5453.html. Mathematical Programming.
Feltenmark, S., & Kiwiel, K. C. (2000). Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems. SIAM Journal on Optimization, 10(3), 697–721.
Fisher, M. L. (1973). Optimal solution of scheduling problems using Lagrange multipliers: part I. Operations Research, 21, 1114–1127.
Geoffrion, A. M. (1974). Lagrangian relaxation for integer programming. Mathematical Programming Study, 2, 82–114.
Goemans, M. X. (1997). Semidefinite programming in combinatorial optimization. Mathematical Programming, 79, 143–161.
Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 6, 1115–1145.
Goffin, J.-L., Haurie, A., & Vial, J.-P. (1992). Decomposition and nondifferentiable optimization with the projective algorithm. Management Science, 38(2), 284–302.
Grinold, R. C. (1970). Lagrangian subgradients. Management Science, 17(3), 185–188.
Grötschel, M., Lovász, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197.
Held, M., & Karp, R. (1971). The traveling salesman problem and minimum spanning trees: part II. Mathematical Programming, 1(1), 6–25.
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993). Convex analysis and minimization algorithms. Heidelberg: Springer.
Hiriart-Urruty, J.-B., & Lemaréchal, C. (2001). Fundamentals of convex analysis. Heidelberg: Springer.
Horn, R. A., & Johnson, C. R. (1989). Matrix analysis. Cambridge: Cambridge University Press (new edition, 1999).
Kiwiel, K. C. (1986). A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA Journal of Numerical Analysis, 6, 137–152.
Kiwiel, K. C. (2004, in press). An inexact bundle approach to cutting stock problems. Technical report, Systems Research Institute, Warsaw. INFORMS J. of Computing.
Kiwiel, K. C. (2006). A proximal bundle method with approximate subgradient linearizations. SIAM Journal on Optimization, 16(4), 1007–1023.
Kiwiel, K. C., & Lemaréchal, C. (2006, submitted). An inexact conic bundle variant suited to column generation. Open archive http://hal.inria.fr/inria-00109402. Mathematical Programming.
Larsson, T., Patriksson, M., & Strömberg, A. B. (1999). Ergodic, primal convergence in dual subgradient schemes for convex programming. Mathematical Programming, 86(2), 283–312.
Lasdon, L. (1970). Optimization theory for large systems. Macmillan series in operations research.
Lemaréchal, C. (1974). An algorithm for minimizing convex functions. In J. L. Rosenfeld (Ed.), Information processing ’74 (pp. 552–556). Amsterdam: North-Holland.
Lemaréchal, C. (2001). Lagrangian relaxation. In M. Jünger, D. Naddef (Eds.), Computational combinatorial optimization (pp. 112–156). Heidelberg: Springer.
Lemaréchal, C. (2003). The omnipresence of Lagrange. 4OR, 1(1), 7–25.
Lemaréchal, C., Ouorou, A., & Petrou, G. (2006). A bundle-type algorithm for routing in telecommunication data networks. Technical report RR6010, INRIA. https://hal.inria.fr/inria-00110559.
Lemaréchal, C., & Oustry, F. (1999). Semi-definite relaxations and Lagrangian duality with application to combinatorial optimization. Rapport de Recherche 3710, INRIA. http://www.inria.fr/rrrt/rr-3710.html.
Lemaréchal, C., & Renaud, A. (2001). A geometric study of duality gaps, with applications. Mathematical Programming, 90(3), 399–427.
Lemaréchal, C., & Sagastizábal, C. (1997). Variable metric bundle methods: from conceptual to implementable forms. Mathematical Programming, 76(3), 393–410.
Magnanti, T. L., Shapiro, J. F., & Wagner, M. H. (1976). Generalized linear programming solves the dual. Management Science, 22(11), 1195–1203.
Muckstadt, M. A., & Koenig, S. A. (1977). An application of Lagrangian relaxation to scheduling in power-generation systems. Operations Research, 25, 387–403.
Nemirovskii, A. S., & Yudin, D. (1983). Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. New York: Wiley-Interscience (Original Russian: Moscow Nauka, 1979).
Nurminskii, E. A., & Zhelikhovskii, A. A. (1977). ε-Quasigradient method for solving nonsmooth extremal problems. Cybernetics, 13(1), 109–114.
Ouorou, A., Mahey, P., & Vial, J.-P. (2000). A survey of algorithms for convex multicommodity flow problems. Management Science, 47(1), 126–147.
Poljak, S., Rendl, F., & Wolkowicz, H. (1995). A recipe for semidefinite relaxation for (0,1)-quadratic programming. Journal of Global Optimization, 7, 51–73.
Reeves, C. R. (1993). Modern heuristic techniques for combinatorial problems. New York: Blackwell Scientific.
Sagastizábal, C., Bahiense, L., & Maculan, N. (2002). The volume algorithm revisited: relation with bundle methods. Mathematical Programming, 94(1), 41–69.
Shor, N. Z. (1985). Minimization methods for non-differentiable functions. Berlin: Springer.
Stetsenko, S. I., & Shor, N. Z. (1984). The connection between Lovász’ estimates with dual estimates in quadratic Boolean problems. In Solutions methods of nonlinear and discrete programming, proceedings of the seminar “National Council on Cybernetics”. Kiev: Institute of Cybernetics.
Vandenberghe, L., & Boyd, S. (1996). Semidefinite programming. SIAM Review, 38(1), 49–95.
Vanderbeck, F. (2000). On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1), 111–128.
Wolfe, P. (1975). A method of conjugate subgradients for minimizing nondifferentiable functions. Mathematical Programming Study, 3, 145–173.
Wolsey, L. A. (1998). Integer programming. New York: Wiley-Interscience.
Author information
Authors and Affiliations
Corresponding author
Additional information
This is an updated version of the paper that appeared in 4OR, 1(1), 7–25 (2003).
Rights and permissions
About this article
Cite this article
Lemaréchal, C. The omnipresence of Lagrange. Ann Oper Res 153, 9–27 (2007). https://doi.org/10.1007/s10479-007-0169-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0169-1