IDEAS home Printed from https://ideas.repec.org/h/spr/sprchp/978-0-387-25486-9_9.html
   My bibliography  Save this book chapter

Combining Column Generation and Lagrangian Relaxation

In: Column Generation

Author

Listed:
  • Dennis Huisman

    (Erasmus University Rotterdam)

  • Raf Jans

    (Erasmus University Rotterdam)

  • Marc Peeters
  • Albert P.M. Wagelmans

    (Erasmus University Rotterdam)

Abstract

Although the possibility to combine column generation and Lagrangian relaxation has been known for quite some time, it has only recently been exploited in algorithms. In this paper, we discuss ways of combining these techniques. We focus on solving the LP relaxation of the Dantzig-Wolfe master problem. In a first approach we apply Lagrangian relaxation directly to this extended formulation, i.e. no simplex method is used. In a second one, we use Lagrangian relaxation to generate new columns, that is Lagrangian relaxation is applied to the compact formulation. We will illustrate the ideas behind these algorithms with an application in lot-sizing. To show the wide applicability of these techniques, we also discuss applications in integrated vehicle and crew scheduling, plant location and cutting stock problems.

Suggested Citation

  • Dennis Huisman & Raf Jans & Marc Peeters & Albert P.M. Wagelmans, 2005. "Combining Column Generation and Lagrangian Relaxation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 247-270, Springer.
    • Handle: RePEc:spr:sprchp:978-0-387-25486-9_9
    DOI: 10.1007/0-387-25486-2_9
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

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


    Cited by:

    1. Eliashberg, Jehoshua & Hegie, Quintus & Ho, Jason & Huisman, Dennis & Miller, Steven J. & Swami, Sanjeev & Weinberg, Charles B. & Wierenga, Berend, 2009. "Demand-driven scheduling of movies in a multiplex," International Journal of Research in Marketing, Elsevier, vol. 26(2), pages 75-88.
    2. Lucas P. Veelenturf & Daniel Potthoff & Dennis Huisman & Leo G. Kroon & Gábor Maróti & Albert P. M. Wagelmans, 2016. "A Quasi-Robust Optimization Approach for Crew Rescheduling," Transportation Science, INFORMS, vol. 50(1), pages 204-215, February.
    3. Veelenturf, L.P. & Potthoff, D. & Huisman, D. & Kroon, L.G. & Maróti, G. & Wagelmans, A.P.M., 2013. "A Quasi-Robust Optimization Approach for Resource Rescheduling," Econometric Institute Research Papers 50110, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Lixin Tang & Gongshu Wang & Jiyin Liu & Jingyi Liu, 2011. "A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(4), pages 370-388, June.
    5. Eliashberg, J. & Hegie, Q. & Ho, J. & Huisman, D. & Miller, S.J. & Swami, S. & Weinberg, C.B. & Wierenga, B., 2007. "Demand-driven scheduling of movies in a multiplex," Econometric Institute Research Papers EI 2007-17, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    6. Mariana Escallón-Barrios & Daniel Castillo-Gomez & Jorge Leal & Carlos Montenegro & Andrés L. Medaglia, 2022. "Improving harvesting operations in an oil palm plantation," Annals of Operations Research, Springer, vol. 314(2), pages 411-449, July.
    7. Wang, Julong & Liu, Zhixue & Li, Feng, 2024. "Integrated production and transportation scheduling problem under nonlinear cost structures," European Journal of Operational Research, Elsevier, vol. 313(3), pages 883-904.
    8. Koza, David Franz, 2019. "Liner shipping service scheduling and cargo allocation," European Journal of Operational Research, Elsevier, vol. 275(3), pages 897-915.
    9. Silvio Alexandre de Araujo & Bert De Reyck & Zeger Degraeve & Ioannis Fragkos & Raf Jans, 2015. "Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 431-448, August.
    10. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Tao, Siyu & Zhang, Bojian & Peng, Qiyuan, 2024. "A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
    11. Annette Chmielewski & Boris Naujoks & Michael Janas & Uwe Clausen, 2009. "Optimizing the Door Assignment in LTL-Terminals," Transportation Science, INFORMS, vol. 43(2), pages 198-210, May.
    12. Thomas, Anu & Venkateswaran, Jayendran & Singh, Gaurav & Krishnamoorthy, Mohan, 2014. "A resource constrained scheduling problem with multiple independent producers and a single linking constraint: A coal supply chain example," European Journal of Operational Research, Elsevier, vol. 236(3), pages 946-956.
    13. Huisman, Dennis, 2007. "A column generation approach for the rail crew re-scheduling problem," European Journal of Operational Research, Elsevier, vol. 180(1), pages 163-173, July.

    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:sprchp:978-0-387-25486-9_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.

    We have no bibliographic references for this item. You can help adding them by using 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.