Solving Cutting Stock Problems via an Extended Ryan-Foster Branching Scheme and Fast Column Generation

References

• Baldacci R, Coniglio S, Cordeau JF, Furini F (2024) A numerically exact algorithm for the bin-packing problem. INFORMS J. Comput. 36(1):141–162.Link, Google Scholar
• Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur. J. Oper. Res. 171(1):85–106.Crossref, Google Scholar
• Belvaux G, Wolsey LA (2000) bc—Prod: A specialized branch-and-cut system for lot-sizing problems. Management Sci. 46(5):724–738.Link, Google Scholar
• Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463.Link, Google Scholar
• Borges YG, Miyazawa FK, Schouery RC, Xavier EC (2020) Exact algorithms for class-constrained packing problems. Computers Indust. Engrg. 144:106455.Crossref, Google Scholar
• Bulhões T, Pessoa A, Protti F, Uchoa E (2018) On the complete set packing and set partitioning polytopes: Properties and rank 1 facets. Oper. Res. Lett. 46(4):389–392.Crossref, Google Scholar
• Ceselli A, Righini G (2008) An optimization algorithm for the ordered open-end bin-packing problem. Oper. Res. 56(2):425–436.Link, Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• da Silva RFF, Schouery RCS (2025) Solving cutting stock problems via an extended Ryan-Foster branching scheme and fast column generation. https://doi.org/10.1287/ijoc.2023.0399.cd, https://github.com/INFORMSJoC/2023.0399.Google Scholar
• de Lima VL, Iori M, Miyazawa FK (2023) Exact solution of network flow models with strong relaxations. Math. Programming 197:813–846.Crossref, Google Scholar
• Dell’Amico M, Iori M, Martello S, Monaci M (2008) Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS J. Comput. 20(3):333–344.Link, Google Scholar
• Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32(1):101–119.Link, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2018) BPPLIB: A library for bin packing and cutting stock problems. Optim. Lett. 12(2):235–250.Crossref, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1):23–47.Crossref, Google Scholar
• Gharbi A, Bamatraf K (2022) An improved arc flow model with enhanced bounds for minimizing the makespan in identical parallel machine scheduling. Processes 10(11).Crossref, Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1):175–194.Link, Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Iori M, de Lima VL, Martello S, Monaci M (2022) 2DPackLib: A two-dimensional cutting and packing library. Optim. Lett. 16(2):471–480.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Korbacher L, Irnich S, Martinovic J, Strasdat N (2023) Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model. Discrete Appl. Math. 334:145–162.Crossref, Google Scholar
• Martinovic J, Delorme M, Iori M, Scheithauer G, Strasdat N (2020) Improved flow-based formulations for the skiving stock problem. Comput. Oper. Res. 113:104770.Crossref, Google Scholar
• Mrad M, Souayah N (2018) An arc-flow model for the makespan minimization problem on identical parallel machines. IEEE Access 6:5300–5307.Crossref, Google Scholar
• Mrad M, Meftahi I, Haouari M (2013) A branch-and-price algorithm for the two-stage guillotine cutting stock problem. J. Oper. Res. Soc. 64(5):629–637.Crossref, Google Scholar
• Peeters M, Degraeve Z (2006) Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem. Eur. J. Oper. Res. 170(2):416–439.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Scheithauer G, Terno J (1995) The modified integer round-up property of the one-dimensional cutting stock problem. Eur. J. Oper. Res. 84(3):562–571. Crossref, Google Scholar
• Silva R, Schouery R (2024) A branch-and-cut-and-price algorithm for cutting stock and related problems. Rev. Eletrônica Iniciação Científica Comput. 22(1):31–40.Google Scholar
• Valério de Carvalho JM (1999) Exact solution of bin‐packing problems using column generation and branch‐and‐bound. Ann. Oper. Res. 86:629–659.Crossref, Google Scholar
• Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. 9(3):211–228.Crossref, Google Scholar
• Vance PH, Barnhart C, Johnson EL, Nemhauser GL (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. 3(2):111–130.Crossref, Google Scholar
• Vanderbeck F (2011) Branching in branch-and-price: A generic scheme. Math. Programming 130(2):249–294.Crossref, Google Scholar
• Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar