IDEAS home Printed from https://ideas.repec.org/p/jgu/wpaper/1407.html
   My bibliography  Save this paper

Dual Inequalities for Stabilized Column Generation Revisited

Author

Listed:
  • Timo Gschwind

    (Johannes Gutenberg-Universitaet Mainz, Germany)

  • Stefan Irnich

    (Johannes Gutenberg-Universitaet Mainz, Germany)

Abstract

Column generation (CG) models have several advantages over compact formulations, namely, they provide better LP bounds, may eliminate symmetry, and can hide non-linearities in their subproblems. However, users also encounter drawbacks in the form of slow convergency a.k.a. the tailing-off effect and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor, H., Desrosiers, J., and Valério de Carvalho, J. M. (2006). Dual-optimal inequalities for stabilized column generation. Operations Research, 54(3), 454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize their results, provide new classes of (deep) DOIs, and show the applicability to other problems (vector packing, vertex coloring, bin packing with conflicts). We also suggest the dynamic addition of violated dual inequalities in a cutting-plane fashion and the use of dual inequalities that are not necessarily (deep) DOIs. In the latter case, a recovery procedure is needed to restore primal feasibility. Computational results proving the usefulness of the methods are presented.

Suggested Citation

  • 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.
    • Handle: RePEc:jgu:wpaper:1407
    as

    Download full text from publisher

    File URL: https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1407.pdf
    File Function: First version, 2014
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Scholl, Armin & Klein, Robert & Jürgens, Christian, 1996. "BISON : a fast hybrid procedure for exactly solving the one-dimensional bin packing problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 49135, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Alberto Caprara & Fabio Furini & Enrico Malaguti, 2013. "Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 560-571, August.
    3. Alves, Cláudio & de Carvalho, José Valério & Clautiaux, François & Rietz, Jürgen, 2014. "Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem," European Journal of Operational Research, Elsevier, vol. 233(1), pages 43-63.
    4. Hatem Ben Amor & José Valério de Carvalho, 2005. "Cutting Stock Problems," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 131-161, Springer.
    5. Ruslan Sadykov & François Vanderbeck, 2013. "Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 244-255, May.
    6. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    7. Desrosiers, Jacques & Gauthier, Jean Bertrand & Lübbecke, Marco E., 2014. "Row-reduced column generation for degenerate master problems," European Journal of Operational Research, Elsevier, vol. 236(2), pages 453-460.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    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. R. S. Garfinkel & G. L. Nemhauser, 1969. "The Set-Partitioning Problem: Set Covering with Equality Constraints," Operations Research, INFORMS, vol. 17(5), pages 848-856, October.
    14. Hatem Ben Amor & Jacques Desrosiers & José Manuel Valério de Carvalho, 2006. "Dual-Optimal Inequalities for Stabilized Column Generation," Operations Research, INFORMS, vol. 54(3), pages 454-463, June.
    15. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    16. Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
    17. Claudia Bode & Stefan Irnich, 2012. "Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem," Operations Research, INFORMS, vol. 60(5), pages 1167-1182, October.
    18. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    19. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    20. Albert E. Fernandes Muritiba & Manuel Iori & Enrico Malaguti & Paolo Toth, 2010. "Algorithms for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 401-415, August.
    21. Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
    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. Timo Gschwind & Stefan Irnich, 2014. "Stabilized Column Generation for the Temporal Knapsack Problem using Dual- Optimal Inequalities," Working Papers 1413, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 13 Nov 2014.
    2. David Sayah, 2015. "Approximate Linear Programming in Network Revenue Management with Multiple Modes," Working Papers 1518, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    2. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    3. 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.
    4. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    5. Timo Gschwind & Stefan Irnich, 2014. "Stabilized Column Generation for the Temporal Knapsack Problem using Dual- Optimal Inequalities," Working Papers 1413, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 13 Nov 2014.
    6. Timo Gschwind & Stefan Irnich, 2017. "Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 541-556, March.
    7. Heßler, Katrin & Gschwind, Timo & Irnich, Stefan, 2018. "Stabilized branch-and-price algorithms for vector packing problems," European Journal of Operational Research, Elsevier, vol. 271(2), pages 401-419.
    8. Katrin Heßler & Timo Gschwind & Stefan Irnich, 2017. "Stabilized Branch-and-Price Algorithms for Vector Packing Problems," Working Papers 1713, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    10. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    11. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    12. Sebastian Kraul & Markus Seizinger & Jens O. Brunner, 2023. "Machine Learning–Supported Prediction of Dual Variables for the Cutting Stock Problem with an Application in Stabilized Column Generation," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 692-709, May.
    13. 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.
    14. 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.
    15. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    16. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    17. Hu, Qian & Zhu, Wenbin & Qin, Hu & Lim, Andrew, 2017. "A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function," European Journal of Operational Research, Elsevier, vol. 260(1), pages 70-80.
    18. Bouarab, Hocine & El Hallaoui, Issmail & Metrane, Abdelmoutalib & Soumis, François, 2017. "Dynamic constraint and variable aggregation in column generation," European Journal of Operational Research, Elsevier, vol. 262(3), pages 835-850.
    19. Stefano Gualandi & Federico Malucelli, 2013. "Constraint Programming-based Column Generation," Annals of Operations Research, Springer, vol. 204(1), pages 11-32, April.
    20. Adil Tahir & Guy Desaulniers & Issmail El Hallaoui, 2019. "Integral column generation for the set partitioning problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 713-744, December.

    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:jgu:wpaper:1407. 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: Research Unit IPP (email available below). General contact details of provider: https://edirc.repec.org/data/vlmaide.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.