IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v53y2005i6p1007-1023.html
   My bibliography  Save this article

Selected Topics in Column Generation

Author

Listed:
  • Marco E. Lübbecke

    (Technische Universität Berlin, Institut für Mathematik, Sekr. MA 6-1, Straße des 17. Juni 136, D-10623 Berlin, Germany)

  • Jacques Desrosiers

    (HEC Montréal and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7)

Abstract

Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large-scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not yet found in textbooks. We emphasize the growing understanding of the dual point of view, which has brought considerable progress to the column generation theory and practice. It stimulated careful initializations, sophisticated solution techniques for the restricted master problem and subproblem, as well as better overall performance. Thus, the dual perspective is an ever recurring concept in our “selected topics.”

Suggested Citation

  • Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    • Handle: RePEc:inm:oropre:v:53:y:2005:i:6:p:1007-1023
    DOI: 10.1287/opre.1050.0234
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1050.0234
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1050.0234?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
    ---><---

    References listed on IDEAS

    as
    1. Hansen, Pierre & Jaumard, Brigitte & de Aragao, Marcus Poggi, 1998. "Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem," European Journal of Operational Research, Elsevier, vol. 108(3), pages 671-683, August.
    2. Chu, Hai D. & Gelman, Eric & Johnson, Ellis L., 1997. "Solving large scale crew scheduling problems," European Journal of Operational Research, Elsevier, vol. 97(2), pages 260-268, March.
    3. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Kyungchul Park & Seokhoon Kang & Sungsoo Park, 1996. "An Integer Programming Approach to the Bandwidth Packing Problem," Management Science, INFORMS, vol. 42(9), pages 1277-1291, September.
    6. Martin Savelsbergh, 1997. "A Branch-and-Price Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 45(6), pages 831-841, December.
    7. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    8. François Vanderbeck, 2005. "Implementing Mixed Integer Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 331-358, Springer.
    9. Anuj Mehrotra & Michael A. Trick, 1996. "A Column Generation Approach for Graph Coloring," INFORMS Journal on Computing, INFORMS, vol. 8(4), pages 344-354, November.
    10. L. V. Kantorovich, 1960. "Mathematical Methods of Organizing and Planning Production," Management Science, INFORMS, vol. 6(4), pages 366-422, July.
    11. Celso C. Ribeiro & François Soumis, 1994. "A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 42(1), pages 41-52, February.
    12. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    13. Martin Desrochers & François Soumis, 1989. "A Column Generation Approach to the Urban Transit Crew Scheduling Problem," Transportation Science, INFORMS, vol. 23(1), pages 1-13, February.
    14. VAN ROY, Tony J., 1983. "Cross decomposition for mixed integer programming," LIDAM Reprints CORE 496, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    16. A. A. Farley, 1990. "A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems," Operations Research, INFORMS, vol. 38(5), pages 922-923, October.
    17. Issmail Elhallaoui & Daniel Villeneuve & François Soumis & Guy Desaulniers, 2005. "Dynamic Aggregation of Set-Partitioning Constraints in Column Generation," Operations Research, INFORMS, vol. 53(4), pages 632-645, August.
    18. R. E. Marsten & W. W. Hogan & J. W. Blankenship, 1975. "The B oxstep Method for Large-Scale Optimization," Operations Research, INFORMS, vol. 23(3), pages 389-405, June.
    19. Moshe Eben-Chaime & Craig A. Tovey & Jane C. Ammons, 1996. "Circuit Partitioning Via Set Partitioning and Column Generation," Operations Research, INFORMS, vol. 44(1), pages 65-76, February.
    20. Roy E. Marsten, 1975. "The Use of the Box Step Method in Discrete Optimization," NBER Working Papers 0086, National Bureau of Economic Research, Inc.
    21. Michel Gamache & François Soumis & Gérald Marquis & Jacques Desrosiers, 1999. "A Column Generation Approach for Large-Scale Aircrew Rostering Problems," Operations Research, INFORMS, vol. 47(2), pages 247-263, April.
    22. Ribeiro, Celso Carneiro & Minoux, Michel & Penna, Manoel Camillo, 1989. "An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment," European Journal of Operational Research, Elsevier, vol. 41(2), pages 232-239, July.
    23. Warren E. Walker, 1969. "Letter to the Editor—A Method for Obtaining the Optimal Dual Solution to a Linear Program Using the Dantzig-Wolfe Decomposition," Operations Research, INFORMS, vol. 17(2), pages 368-370, April.
    24. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    25. Guy Desaulniers & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & François Soumis, 1997. "Daily Aircraft Routing and Scheduling," Management Science, INFORMS, vol. 43(6), pages 841-855, June.
    26. John W. Mamer & Richard D. McBride, 2000. "A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem," Management Science, INFORMS, vol. 46(5), pages 693-709, May.
    27. Cynthia Barnhart & Rina R. Schneur, 1996. "Air Network Design for Express Shipment Service," Operations Research, INFORMS, vol. 44(6), pages 852-863, December.
    28. Niklas Kohl & Oli B. G. Madsen, 1997. "An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation," Operations Research, INFORMS, vol. 45(3), pages 395-406, June.
    29. Vanderbeck, F. & Wolsey, L. A., 1996. "An exact algorithm for IP column generation," LIDAM Reprints CORE 1242, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    30. Ioachim, Irina & Desrosiers, Jacques & Soumis, Francois & Belanger, Nicolas, 1999. "Fleet assignment and routing with schedule synchronization constraints," European Journal of Operational Research, Elsevier, vol. 119(1), pages 75-90, November.
    31. Crama, Yves & Oerlemans, Alwin G., 1994. "A column generation approach to job grouping for flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 78(1), pages 58-80, October.
    32. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    33. Goffin, J. -L. & Haurie, A. & Vial, J. -Ph. & Zhu, D. L., 1993. "Using central prices in the decomposition of linear programs," European Journal of Operational Research, Elsevier, vol. 64(3), pages 393-409, February.
    34. 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.
    35. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    36. Robert E. Bixby & John W. Gregory & Irvin J. Lustig & Roy E. Marsten & David F. Shanno, 1992. "Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods," Operations Research, INFORMS, vol. 40(5), pages 885-897, October.
    37. Michel Gamache & François Soumis & Daniel Villeneuve & Jacques Desrosiers & Éric Gélinas, 1998. "The Preferential Bidding System at Air Canada," Transportation Science, INFORMS, vol. 32(3), pages 246-255, August.
    38. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    39. Cynthia Barnhart & Natashia L. Boland & Lloyd W. Clarke & Ellis L. Johnson & George L. Nemhauser & Rajesh G. Shenoi, 1998. "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, INFORMS, vol. 32(3), pages 208-220, August.
    40. Niklas Kohl & Jacques Desrosiers & Oli B. G. Madsen & Marius M. Solomon & François Soumis, 1999. "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 33(1), pages 101-116, February.
    41. Robert E. Bixby, 2002. "Solving Real-World Linear Programs: A Decade and More of Progress," Operations Research, INFORMS, vol. 50(1), pages 3-15, February.
    42. Marco E. Lübbecke & Uwe T. Zimmermann, 2003. "Engine Routing and Scheduling at Industrial In-Plant Railroads," Transportation Science, INFORMS, vol. 37(2), pages 183-197, May.
    43. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    44. A. Erdmann & A. Nolte & A. Noltemeier & R. Schrader, 2001. "Modeling and Solving an Airline Schedule Generation Problem," Annals of Operations Research, Springer, vol. 107(1), pages 117-142, October.
    45. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    Full references (including those not matched with items on IDEAS)

    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. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    2. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    3. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    4. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    5. 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.
    6. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    7. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    8. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    9. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    10. Valerio de Carvalho, J. M., 2002. "LP models for bin packing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 253-273, September.
    11. Zeger Degraeve & Marc Peeters, 2003. "Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 58-81, February.
    12. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, August.
    13. Rosemary T. Berger & Collette R. Coullard & Mark S. Daskin, 2007. "Location-Routing Problems with Distance Constraints," Transportation Science, INFORMS, vol. 41(1), pages 29-43, February.
    14. Osman Ou{g}uz, 2002. "Generalized Column Generation for Linear Programming," Management Science, INFORMS, vol. 48(3), pages 444-452, March.
    15. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    16. Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    17. Timo Gschwind & Stefan Irnich, 2014. "Dual Inequalities for Stabilized Column Generation Revisited," Working Papers 1407, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 23 Jul 2014.
    18. Issmail Elhallaoui & Daniel Villeneuve & François Soumis & Guy Desaulniers, 2005. "Dynamic Aggregation of Set-Partitioning Constraints in Column Generation," Operations Research, INFORMS, vol. 53(4), pages 632-645, August.
    19. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.
    20. Gondzio, Jacek & González-Brevis, Pablo & Munari, Pedro, 2013. "New developments in the primal–dual column generation technique," European Journal of Operational Research, Elsevier, vol. 224(1), pages 41-51.

    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:inm:oropre:v:53:y:2005:i:6:p:1007-1023. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.