IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v139y2005i1p163-19310.1007-s10479-005-3447-9.html
   My bibliography  Save this article

About Lagrangian Methods in Integer Optimization

Author

Listed:
  • Antonio Frangioni

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. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Antonio Frangioni, 2005. "About Lagrangian Methods in Integer Optimization," Annals of Operations Research, Springer, vol. 139(1), pages 163-193, October.
    • Handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:163-193:10.1007/s10479-005-3447-9
    DOI: 10.1007/s10479-005-3447-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-3447-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-3447-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Richard D. McBride, 1998. "Advances in Solving the Multicommodity-Flow Problem," Interfaces, INFORMS, vol. 28(2), pages 32-41, April.
    2. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    3. X. Zhao & P.B. Luh, 2002. "New Bundle Methods for Solving Lagrangian Relaxation Dual Problems," Journal of Optimization Theory and Applications, Springer, vol. 113(2), pages 373-397, May.
    4. Cynthia Barnhart, 1993. "Dual‐ascent methods for large‐scale multicommodity flow problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 305-324, April.
    5. Nesterov, Y., 1995. "Complexity estimates of some cutting plane methods based on the analytic barrier," LIDAM Reprints CORE 1167, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Judith M. Farvolden & Warren B. Powell, 1994. "Subgradient Methods for the Service Network Design Problem," Transportation Science, INFORMS, vol. 28(3), pages 256-272, August.
    7. Guignard, Monique & Rosenwein, Moshe B., 1989. "An application-oriented guide for designing Lagrangean dual ascent algorithms," European Journal of Operational Research, Elsevier, vol. 43(2), pages 197-205, November.
    8. Samer Takriti & John R. Birge, 2000. "Lagrangian Solution Techniques and Bounds for Loosely Coupled Mixed-Integer Stochastic Programs," Operations Research, INFORMS, vol. 48(1), pages 91-98, February.
    9. Lemaréchal, C. & Nemirovskii, A. & Nesterov, Y., 1995. "New variants of bundle methods," LIDAM Reprints CORE 1166, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Guignard, Monique, 1998. "Efficient cuts in Lagrangean `Relax-and-cut' schemes," European Journal of Operational Research, Elsevier, vol. 105(1), pages 216-223, February.
    11. Suk-Gwon Chang & Bezalel Gavish, 1995. "Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems," Operations Research, INFORMS, vol. 43(1), pages 43-57, February.
    12. Luis Gouveia, 1995. "A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem," Operations Research, INFORMS, vol. 43(1), pages 130-141, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Pascale Bendotti & Pierre Fouilhoux & Cécile Rottner, 2019. "On the complexity of the Unit Commitment Problem," Annals of Operations Research, Springer, vol. 274(1), pages 119-130, March.
    2. Pascale Bendotti & Pierre Fouilhoux & Cécile Rottner, 2018. "The min-up/min-down unit commitment polytope," Journal of Combinatorial Optimization, Springer, vol. 36(3), pages 1024-1058, October.
    3. Antonio Frangioni & Claudio Gentile & Enrico Grande & Andrea Pacifici, 2011. "Projected Perspective Reformulations with Applications in Design Problems," Operations Research, INFORMS, vol. 59(5), pages 1225-1232, October.
    4. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    5. Knudsen, Brage Rugstad & Whitson, Curtis H. & Foss, Bjarne, 2014. "Shale-gas scheduling for natural-gas supply in electric power production," Energy, Elsevier, vol. 78(C), pages 165-182.
    6. Sanjay Dominik Jena & Jean-François Cordeau & Bernard Gendron, 2017. "Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 388-404, August.
    7. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    8. Nasini, Stefano & Nessah, Rabia, 2024. "Time-flexible min completion time variance in a single machine by quadratic programming," European Journal of Operational Research, Elsevier, vol. 312(2), pages 427-444.
    9. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).
    10. Tonbari, Mohamed El & Ahmed, Shabbir, 2023. "Consensus-based Dantzig-Wolfe decomposition," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1441-1456.
    11. Carosi, Samuela & Frangioni, Antonio & Galli, Laura & Girardi, Leopoldo & Vallese, Giuliano, 2019. "A matheuristic for integrated timetabling and vehicle scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 99-124.
    12. Igor Litvinchev & Socorro Rangel & Jania Saucedo, 2010. "A Lagrangian bound for many-to-many assignment problems," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 241-257, April.
    13. Lara, Cristiana L. & Mallapragada, Dharik S. & Papageorgiou, Dimitri J. & Venkatesh, Aranya & Grossmann, Ignacio E., 2018. "Deterministic electric power infrastructure planning: Mixed-integer programming model and nested decomposition algorithm," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1037-1054.
    14. Semih Atakan & Kerem Bülbül & Nilay Noyan, 2017. "Minimizing value-at-risk in single-machine scheduling," Annals of Operations Research, Springer, vol. 248(1), pages 25-73, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    2. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2020. "Essentials of numerical nonsmooth optimization," 4OR, Springer, vol. 18(1), pages 1-47, March.
    3. Monique Guignard, 2003. "Lagrangean relaxation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 11(2), pages 151-200, December.
    4. Ming Fan & Jan Stallaert & Andrew B. Whinston, 2003. "Decentralized Mechanism Design for Supply Chain Organizations Using an Auction Market," Information Systems Research, INFORMS, vol. 14(1), pages 1-22, March.
    5. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    6. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    7. Júlíus Atlason & Marina A. Epelman & Shane G. Henderson, 2008. "Optimizing Call Center Staffing Using Simulation and Analytic Center Cutting-Plane Methods," Management Science, INFORMS, vol. 54(2), pages 295-309, February.
    8. Ethem Çanakoğlu & İbrahim Muter & Tevfik Aytekin, 2021. "Integrating Individual and Aggregate Diversity in Top- N Recommendation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 300-318, January.
    9. Slava Sery & Vince Presti & Donald E. Shobrys, 2001. "Optimization Models for Restructuring BASF North America's Distribution System," Interfaces, INFORMS, vol. 31(3), pages 55-65, June.
    10. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    11. Sankaran, Jayaram K., 1995. "Column generation applied to linear programs in course registration," European Journal of Operational Research, Elsevier, vol. 87(2), pages 328-342, December.
    12. Metrane, Abdelmoutalib & Soumis, François & Elhallaoui, Issmail, 2010. "Column generation decomposition with the degenerate constraints in the subproblem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 37-44, November.
    13. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    14. Williams, R. Lynn & Dillion, Carl R. & McCarl, Bruce A., 1992. "An Economic Investigation of Edwards Aquifer Water Use Tradeoffs," WAEA/ WFEA Conference Archive (1929-1995) 321395, Western Agricultural Economics Association.
    15. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    16. Gendreau, Michel & Potvin, Jean-Yves & Smires, Ali & Soriano, Patrick, 2006. "Multi-period capacity expansion for a local access telecommunications network," European Journal of Operational Research, Elsevier, vol. 172(3), pages 1051-1066, August.
    17. Raymond K. Cheung & B. Muralidharan, 2000. "Dynamic Routing for Priority Shipments in LTL Service Networks," Transportation Science, INFORMS, vol. 34(1), pages 86-98, February.
    18. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    19. Fernandes, Lucinda Matos & Gouveia, Luis, 1998. "Minimal spanning trees with a constraint on the number of leaves," European Journal of Operational Research, Elsevier, vol. 104(1), pages 250-261, January.
    20. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.

    More about this item

    Keywords

    Lagrangian dual; integer linear programs;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:163-193:10.1007/s10479-005-3447-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.