IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i2p428-443.html
   My bibliography  Save this article

A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems

Author

Listed:
  • Lijun Wei

    (Key Laboratory of Computer Integrated Manufacturing System, School of Electromechanical Engineering, Guangdong University of Technology, 510006 Guangzhou, People's Republic of China)

  • Zhixing Luo,

    (School of Management and Engineering, Nanjing University, 210093 Nanjing, People’s Republic of China;)

  • Roberto Baldacci

    (Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 119077)

  • Andrew Lim

    (Department of Electrical, Electronic, and Information Engineering "Guglielmo Marconi," University of Bologna, 47521 Cesena, Italy)

Abstract

In this paper, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin-packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, a set of new 500 test instances were proposed for the 1D-BPP, and the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of 1 hour imposed on each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1DBPPs and the subset row inequalities. We describe an ad hoc label-setting algorithm to solve the pricing problem, dominance, and fathoming rules to speed up its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, such as the incompatibility between the items, and therefore, we also apply it to solve the one-dimensional bin-packing problem with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1,003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods and that it successfully closed several open 1D-BPPC instances.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:32:y:2020:i:2:p:428-443
    DOI: 10.1287/ijoc.2018.0867
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0867
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2018.0867?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. 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.
    2. 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).
    3. C. Archetti & M. Bouchard & G. Desaulniers, 2011. "Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows," Transportation Science, INFORMS, vol. 45(3), pages 285-298, August.
    4. Klaus Jansen, 1999. "An Approximation Scheme for Bin Packing with Conflicts," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 363-377, December.
    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. 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.
    7. Enrico Malaguti & Michele Monaci & Paolo Toth, 2008. "A Metaheuristic Approach for the Vertex Coloring Problem," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 302-316, May.
    8. Samir Elhedhli & Lingzi Li & Mariem Gzara & Joe Naoum-Sawaya, 2011. "A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 404-415, August.
    9. L. V. Kantorovich, 1960. "Mathematical Methods of Organizing and Planning Production," Management Science, INFORMS, vol. 6(4), pages 366-422, July.
    10. Samuel Eilon & Nicos Christofides, 1971. "The Loading Problem," Management Science, INFORMS, vol. 17(5), pages 259-268, January.
    11. G Scheithauer & J Terno & A Müller & G Belov, 2001. "Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(12), pages 1390-1401, December.
    12. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    13. M. L. Wolfson, 1965. "Selecting the Best Lengths to Stock," Operations Research, INFORMS, vol. 13(4), pages 570-585, August.
    14. 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.
    15. Belov, G. & Scheithauer, G., 2006. "A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting," European Journal of Operational Research, Elsevier, vol. 171(1), pages 85-106, May.
    16. Scheithauer, Guntram & Terno, Johannes, 1995. "The modified integer round-up property of the one-dimensional cutting stock problem," European Journal of Operational Research, Elsevier, vol. 84(3), pages 562-571, August.
    17. 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.
    18. 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.
    19. Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    20. 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.
    21. Zeger Degraeve & Linus Schrage, 1999. "Optimal Integer Solutions to Industrial Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 406-419, November.
    22. Andrea Bettinelli & Valentina Cacchiani & Enrico Malaguti, 2017. "A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 457-473, August.
    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. Barkel, Mathijs & Delorme, Maxence & Malaguti, Enrico & Monaci, Michele, 2025. "Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation," European Journal of Operational Research, Elsevier, vol. 320(1), pages 57-68.
    2. Boccia, Maurizio & Masone, Adriano & Sterle, Claudio & Murino, Teresa, 2023. "The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach," European Journal of Operational Research, Elsevier, vol. 307(2), pages 590-603.
    3. Chen, Yanru & Gao, Mujin & Zhang, Zongcheng & Li, Junheng & Wahab, M.I.M. & Jiang, Yangsheng, 2025. "Contextual bandits learning-based branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with conflicts and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    4. Zhou, Yangming & Qu, Chenhui & Wu, Qinghua & Kou, Yawen & Jiang, Zhibin & Zhou, MengChu, 2024. "A bilevel hybrid iterated search approach to soft-clustered capacitated arc routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    5. Wang, Ting & Hu, Qian & Lim, Andrew, 2022. "An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs," European Journal of Operational Research, Elsevier, vol. 300(1), pages 20-34.
    6. Baldacci, Roberto & Hoshino, Edna A. & Hill, Alessandro, 2023. "New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems," European Journal of Operational Research, Elsevier, vol. 307(2), pages 538-553.
    7. Shaoxiang Zheng & Naiming Xie & Qiao Wu, 2025. "An exact approach for bi-objective non-identical batch processing machines scheduling," Annals of Operations Research, Springer, vol. 346(3), pages 2307-2347, March.
    8. Renan F. F. Silva & Yulle G. F. Borges & Rafael C. S. Schouery, 2024. "Fast neighborhood search heuristics for the colored bin packing problem," Annals of Operations Research, Springer, vol. 343(1), pages 125-152, December.
    9. Amin Abbasi-Pooya & Michael T. Lash, 2024. "The third party logistics provider freight management problem: a framework and deep reinforcement learning approach," Annals of Operations Research, Springer, vol. 339(1), pages 965-1024, August.
    10. Akçay, Fatih Burak & Delorme, Maxence, 2025. "Solving the parallel processor scheduling and bin packing problems with contiguity constraints: Mathematical models and computational studies," European Journal of Operational Research, Elsevier, vol. 323(3), pages 701-723.
    11. Ekici, Ali, 2023. "A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1007-1020.
    12. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.

    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. 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.
    2. B. S. C. Campello & C. T. L. S. Ghidini & A. O. C. Ayres & W. A. Oliveira, 2022. "A residual recombination heuristic for one-dimensional cutting stock problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 194-220, April.
    3. Renatha Capua & Yuri Frota & Luiz Satoru Ochi & Thibaut Vidal, 2018. "A study on exponential-size neighborhoods for the bin packing problem with conflicts," Journal of Heuristics, Springer, vol. 24(4), pages 667-695, August.
    4. Chen, Yanru & Gao, Mujin & Zhang, Zongcheng & Li, Junheng & Wahab, M.I.M. & Jiang, Yangsheng, 2025. "Contextual bandits learning-based branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with conflicts and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    5. Ekici, Ali, 2023. "A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1007-1020.
    6. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    7. John Martinovic, 2022. "A note on the integrality gap of cutting and skiving stock instances," 4OR, Springer, vol. 20(1), pages 85-104, March.
    8. Maxence Delorme & Manuel Iori, 2020. "Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 101-119, January.
    9. John Martinovic & Markus Hähnel & Guntram Scheithauer & Waltenegus Dargie, 2022. "An introduction to stochastic bin packing-based server consolidation with conflicts," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(2), pages 296-331, July.
    10. 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.
    11. Krzysztof C. Kiwiel, 2010. "An Inexact Bundle Approach to Cutting-Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 131-143, February.
    12. Borja Ena & Alberto Gomez & Borja Ponte & Paolo Priore & Diego Diaz, 2022. "Homogeneous grouping of non-prime steel products for online auctions: a case study," Annals of Operations Research, Springer, vol. 315(1), pages 591-621, August.
    13. Belov, G. & Scheithauer, G., 2006. "A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting," European Journal of Operational Research, Elsevier, vol. 171(1), pages 85-106, May.
    14. Schepler, Xavier & Rossi, André & Gurevsky, Evgeny & Dolgui, Alexandre, 2022. "Solving robust bin-packing problems with a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 831-843.
    15. 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.
    16. Orlando Rivera Letelier & François Clautiaux & Ruslan Sadykov, 2022. "Bin Packing Problem with Time Lags," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2249-2270, July.
    17. Artur Pessoa & Ruslan Sadykov & Eduardo Uchoa, 2021. "Solving Bin Packing Problems Using VRPSolver Models," SN Operations Research Forum, Springer, vol. 2(2), pages 1-25, June.
    18. Daniel Kowalczyk & Roel Leus, 2017. "An exact algorithm for parallel machine scheduling with conflicts," Journal of Scheduling, Springer, vol. 20(4), pages 355-372, August.
    19. John Martinovic & Markus Hähnel & Guntram Scheithauer & Waltenegus Dargie & Andreas Fischer, 2019. "Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation," 4OR, Springer, vol. 17(2), pages 173-200, June.
    20. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.

    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:orijoc:v:32:y:2020:i:2:p:428-443. 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.