IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v47y2001i6p864-879.html
   My bibliography  Save this article

A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem

Author

Listed:
  • François Vanderbeck

    (MAB, Université de Bordeaux 1, 351, Cours de la Libération, F-33405 Talence Cedex, France)

Abstract

We consider the cutting of rectangular order pieces into stock pieces of specified width and length. The cutting process involves three stages of orthogonal guillotine cutting: Stock pieces are cut into sections that are cut into slits that are cut into order pieces. Restrictions imposed on the cutting process make the combinatorial structure of the problem more complex, but limit the scope of solution space. The objective of the problem is mainly to minimize waste, but our model also accounts for other issues such as aging stock pieces, urgent or optional orders, and fixed setup costs. Our solution approach involves a nested decomposition of the problem and the recursive use of the column-generation technique: We use a column-generation formulation of the problem (Gilmore and Gomory 1965) and the cutting-pattern---generation subproblem is itself solved using a column-generation algorithm. LP-based lower bounds on the minimum cost are computed and, by rounding the LP solution, a feasible solution and associated upper bound is obtained. This approach could in principle be used in a branch-and-bound search to solve the problem to optimality. We report computational results for industrial instances. The algorithm is being used in industry as a production-planning tool.

Suggested Citation

  • François Vanderbeck, 2001. "A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem," Management Science, INFORMS, vol. 47(6), pages 864-879, June.
  • Handle: RePEc:inm:ormnsc:v:47:y:2001:i:6:p:864-879
    DOI: 10.1287/mnsc.47.6.864.9809
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.47.6.864.9809
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.47.6.864.9809?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. & Guimaraes Rodrigues, A. J., 1995. "An LP-based approach to a two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 84(3), pages 580-589, August.
    2. P. C. Gilmore & R. E. Gomory, 1966. "The Theory and Computation of Knapsack Functions," Operations Research, INFORMS, vol. 14(6), pages 1045-1074, December.
    3. 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).
    4. Robert Weismantel, 1996. "Hilbert Bases and the Facets of Special Knapsack Polytopes," Mathematics of Operations Research, INFORMS, vol. 21(4), pages 886-904, November.
    5. David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
    6. 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.
    7. Riehme, Jan & Scheithauer, Guntram & Terno, Johannes, 1996. "The solution of two-stage guillotine cutting stock problems having extremely varying order demands," European Journal of Operational Research, Elsevier, vol. 91(3), pages 543-552, June.
    8. P. C. Gilmore & R. E. Gomory, 1965. "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, INFORMS, vol. 13(1), pages 94-120, February.
    9. Beasley, J. E., 1985. "An algorithm for the two-dimensional assortment problem," European Journal of Operational Research, Elsevier, vol. 19(2), pages 253-261, February.
    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. Cui, Yaodong & Huang, Baixiong, 2012. "Reducing the number of cuts in generating three-staged cutting patterns," European Journal of Operational Research, Elsevier, vol. 218(2), pages 358-365.
    2. Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
    3. Jianyu Long & Zhong Zheng & Xiaoqiang Gao & Panos M. Pardalos & Wanzhe Hu, 2020. "An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem," Annals of Operations Research, Springer, vol. 289(2), pages 291-311, June.
    4. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    5. Samir Elhedhli & Jean-Louis Goffin, 2005. "Efficient Production-Distribution System Design," Management Science, INFORMS, vol. 51(7), pages 1151-1164, July.
    6. Cui, Yaodong & Yang, Liu & Zhao, Zhigang & Tang, Tianbing & Yin, Mengxiao, 2013. "Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction," International Journal of Production Economics, Elsevier, vol. 144(2), pages 432-439.
    7. Silva, Elsa & Alvelos, Filipe & Valério de Carvalho, J.M., 2010. "An integer programming model for two- and three-stage two-dimensional cutting stock problems," European Journal of Operational Research, Elsevier, vol. 205(3), pages 699-708, September.
    8. Yaodong Cui, 2013. "A new dynamic programming procedure for three-staged cutting patterns," Journal of Global Optimization, Springer, vol. 55(2), pages 349-357, February.
    9. Muter, İbrahim & Sezer, Zeynep, 2018. "Algorithms for the one-dimensional two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 20-32.
    10. Tilk, Christian & Drexl, Michael & Irnich, Stefan, 2019. "Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies," European Journal of Operational Research, Elsevier, vol. 276(2), pages 549-565.
    11. Frank Hennig & Bjørn Nygreen & Marco E. Lübbecke, 2012. "Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 298-310, April.
    12. François Clautiaux & Ruslan Sadykov & François Vanderbeck & Quentin Viaud, 2019. "Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 265-297, September.
    13. Alberto Caprara & Andrea Lodi & Michele Monaci, 2005. "Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 150-172, February.
    14. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    15. Kallrath, Julia & Rebennack, Steffen & Kallrath, Josef & Kusche, Rüdiger, 2014. "Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges," European Journal of Operational Research, Elsevier, vol. 238(1), pages 374-389.
    16. Christian Tilk & Michael Drexl & Stefan Irnich, 2018. "Nested Branch-and-Price-and-Cut for Vehicle Routing Problems with Multiple Resource Interdependencies," Working Papers 1801, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Fabio Furini & Enrico Malaguti & Dimitri Thomopulos, 2016. "Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 736-751, November.
    18. Hadj Salem, Khadija & Silva, Elsa & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry," European Journal of Operational Research, Elsevier, vol. 306(2), pages 549-566.
    19. Carolin Bauerhenne & Jonathan Bard & Rainer Kolisch, 2024. "Robust Routing and Scheduling of Home Healthcare Workers: A Nested Branch-and-Price Approach," Papers 2407.06215, arXiv.org.
    20. de Gelder, E.R. & Wagelmans, A.P.M., 2007. "The two-dimensional cutting stock problem within the roller blind production process," Econometric Institute Research Papers EI 2007-47, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    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. Song, X. & Chu, C.B. & Nie, Y.Y. & Bennell, J.A., 2006. "An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1870-1889, December.
    2. Gomory, Ralph, 2016. "Origin and early evolution of corner polyhedra," European Journal of Operational Research, Elsevier, vol. 253(3), pages 543-556.
    3. Sierra-Paradinas, María & Soto-Sánchez, Óscar & Alonso-Ayuso, Antonio & Martín-Campo, F. Javier & Gallego, Micael, 2021. "An exact model for a slitting problem in the steel industry," European Journal of Operational Research, Elsevier, vol. 295(1), pages 336-347.
    4. Furini, Fabio & Malaguti, Enrico & Medina Durán, Rosa & Persiani, Alfredo & Toth, Paolo, 2012. "A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size," European Journal of Operational Research, Elsevier, vol. 218(1), pages 251-260.
    5. Mhand Hifi & Hedi Mhalla & Slim Sadfi, 2005. "Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 10(3), pages 239-260, November.
    6. Andonov, R. & Poirriez, V. & Rajopadhye, S., 2000. "Unbounded knapsack problem: Dynamic programming revisited," European Journal of Operational Research, Elsevier, vol. 123(2), pages 394-407, June.
    7. Yuen, Boon J., 1995. "Improved heuristics for sequencing cutting patterns," European Journal of Operational Research, Elsevier, vol. 87(1), pages 57-64, November.
    8. Leão, Aline A.S. & Santos, Maristela O. & Hoto, Robinson & Arenales, Marcos N., 2011. "The constrained compartmentalized knapsack problem: mathematical models and solution methods," European Journal of Operational Research, Elsevier, vol. 212(3), pages 455-463, August.
    9. Ben Messaoud, Said & Chu, Chengbin & Espinouse, Marie-Laure, 2008. "Characterization and modelling of guillotine constraints," European Journal of Operational Research, Elsevier, vol. 191(1), pages 112-126, November.
    10. Yanasse, Horacio Hideki & Pinto Lamosa, Maria Jose, 2007. "An integrated cutting stock and sequencing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1353-1370, December.
    11. Vera Neidlein & Andrèa C. G. Vianna & Marcos N. Arenales & Gerhard Wäscher, 2008. "The Two-Dimensional, Rectangular, Guillotineable-Layout Cutting Problem with a Single Defect," FEMM Working Papers 08035, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    12. Muter, İbrahim & Sezer, Zeynep, 2018. "Algorithms for the one-dimensional two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 20-32.
    13. Hoto, Robinson & Arenales, Marcos & Maculan, Nelson, 2007. "The one dimensional Compartmentalised Knapsack Problem: A case study," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1183-1195, December.
    14. Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
    15. Cintra, G.F. & Miyazawa, F.K. & Wakabayashi, Y. & Xavier, E.C., 2008. "Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation," European Journal of Operational Research, Elsevier, vol. 191(1), pages 61-85, November.
    16. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    17. 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.
    18. 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.
    19. W. D. D. Madhavee & N. Saldin & U. C. Vaidyarathna & C. J. Jayawardene, 2018. "A Practical Application of the Generalized Cutting Stock Algorithm," Academic Journal of Applied Mathematical Sciences, Academic Research Publishing Group, vol. 4(3), pages 15-21, 03-2018.
    20. Suliman, S.M.A., 2006. "A sequential heuristic procedure for the two-dimensional cutting-stock problem," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 177-185, 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:ormnsc:v:47:y:2001:i:6:p:864-879. 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.