Machine Learning–Supported Prediction of Dual Variables for the Cutting Stock Problem with an Application in Stabilized Column Generation

References

• Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Alves C, Valério de Carvalho JM (2008) A branch-and-price-and-cut algorithm for the pattern minimization problem. RAIRO Oper. Res. 42(4):435–453.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Martin WP Savelsbergh, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bello I, Pham H, Le VQ, Norouzi M, Bengio S (2017) Neural combinatorial optimization with reinforcement learning. Preprint, submitted November 29, 2016, https://arxiv.org/abs/1611.09940.Google Scholar
• Ben Amor H, Desrosiers J (2006) A proximal trust-region algorithm for column generation stabilization. Comput. Oper. Res. 33(4):910–927.Crossref, Google Scholar
• Ben Amor H, Desrosiers JV, de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463.Link, Google Scholar
• Ben Amor HM, Desrosiers J, Frangioni A (2009) On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157(6):1167–1184.Crossref, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bertsimas D, Kallus N (2020) From predictive to prescriptive analytics. Management Sci. 66(3):1025–1044.Link, Google Scholar
• Bonami P, Lodi A, Zarpellon G (2018) Learning a classification of mixed-integer quadratic programming problems. van Hoeve WJ, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, vol. 10848 of SpringerLink Bücher (Springer, Cham, Switzerland), 595–604.Crossref, Google Scholar
• Borchani H, Varando G, Bielza C, Larrañaga P (2015) A survey on multi-output regression. Data Mining Knowledge Discovery 5(5):216–233.Crossref, Google Scholar
• Brunner JO, Stolletz R (2014) Stabilized branch and price with dynamic parameter updating for discontinuous tour scheduling. Comput. Oper. Res. 44:137–145.Crossref, Google Scholar
• Caprara A, Locatelli M, Monaci M (2005) Bidimensional packing by bilinear programming. Jünger M, Kaibel V, eds. Integer Programming and Combinatorial Optimization, vol. 3509 of Lecture Notes in Computer Science (Springer, Berlin), 377–391.Crossref, Google Scholar
• Cheng C, Feiring B, Cheng T (1994) The cutting stock problem—A survey. Internat. J. Production Econom. 36(3):291–305.Crossref, Google Scholar
• Clautiaux F, Alves C, Valério de Carvalho J (2010) A survey of dual-feasible and superadditive functions. Annals Oper. Res. 179(1):317–342.Crossref, Google Scholar
• Clautiaux F, Alves C, Valério de Carvalho J, Rietz J (2011) New stabilization procedures for the cutting stock problem. INFORMS J. Comput. 23(4):530–545.Link, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, 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
• Desrosiers J, Lübbecke ME (2005) A primer in column generation. Desaulniers G, ed. Column Generation (Springer, New York), 1–32.Crossref, Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Mathe. 194(1–3):229–237.Crossref, Google Scholar
• Dyckhoff H (1991) Approaches to cutting and packing problems. Pridham M, ed. Production Research (Taylor & Francis, London), 46–54.Google Scholar
• Fekete SP, Schepers J (2001) New classes of fast lower bounds for bin packing problems. Math. Programming 91(1):11–31.Crossref, Google Scholar
• Fekete SP, Schepers J (2004) A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60(2):311–329.Crossref, Google Scholar
• Gau T, Wäscher G (1995) CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. Eur. J. Oper. Res. 84(3):572–579.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
• Glantz SA, Slinker BK, Neilands TB (2016) Primer of Applied Regression & Analysis of Variance, 3rd ed. (McGraw-Hill Education, New York).Google Scholar
• Goffin JL, Haurie A, Vial JP (1992) Decomposition and nondifferentiable optimization with the projective algorithm. Management Sci. 38(2):284–302.Link, Google Scholar
• Gondzio J, Sarkissian R (1996) Column generation with a primal-dual method. Logilab technical report 96-6, Department of Management Studies, University of Geneva, Geneva.Google Scholar
• Goodfellow I, Bengio Y, Courville A (2016) Deep Learning. Adaptive Computation and Machine Learning (MIT Press, Cambridge, MA).Google Scholar
• Gschwind T, Irnich S (2017) Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities. OR Spectrum 39(2):541–556.Crossref, Google Scholar
• Gurobi Optimization LLC (2021) Gurobi optimizer reference manual. Accessed December 1, 2021, https://www.gurobi.com.Google Scholar
• Hoos HH (2011) Automated algorithm configuration and parameter tuning. Hamadi Y, ed. Autonomous Search (Springer, Berlin), 37–71.Crossref, Google Scholar
• Kantorovich LV (1960) Mathematical methods of organizing and planning production. Management Sci. 6(4):366–422.Link, Google Scholar
• Kartak VM, Ripatti AV, Scheithauer G, Kurz S (2015) Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187:120–129.Crossref, Google Scholar
• Khalil EB, Dilkina B, Nemhauser GL, Ahmed S, Shao Y (2017) Learning to run heuristics in tree search. Sierra C, ed. Proc. Internat. Joint Conf. on Artificial Intelligence (Curran Associates, Red Hook, NY), 659–666.Google Scholar
• Kotsiantis SB, Zaharakis I, Pintelas P (2007) Supervised machine learning: A review of classification techniques. Informatica (Slovenia) 31(3):249–268.Google Scholar
• Kraul S (2023) Problem data of the study. https://github.com/SebastianKraul/Machine-learning-supported-prediction-of-dual-variables-for-the-cutting-stock-problem.Google Scholar
• Kruber M, Lübbecke ME, Parmentier A (2017) Learning when to use a decomposition. Salvagnin D, Lombardi M, eds. Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science (Springer, Cham, Switzerland), 202–210.Crossref, Google Scholar
• LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444.Crossref, Google Scholar
• Lee C, Park S (2011) Chebyshev center-based column generation. Discrete Appl. Math. 159(18):2251–2265.Crossref, Google Scholar
• Lirov Y (1992) Knowledge based approach to the cutting stock problem. Math. Comput. Modelling 16(1):107–125.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Marsten RE, Hogan WW, Blankenship JW (1975) The boxstep method for large-scale optimization. Oper. Res. 23(3):389–405.Link, Google Scholar
• Martello S, Toth P (1990) Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28(1):59–70.Crossref, Google Scholar
• Mazyavkina N, Sviridov S, Ivanov S, Burnaev E (2021) Reinforcement learning for combinatorial optimization: A survey. Comput. Oper. Res. 134:105400.Crossref, Google Scholar
• Modaresi S, Sauré D, Vielma JP (2020) Learning in combinatorial optimization: What and how to explore. Oper. Res. 68(5):1585–1604.Link, Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning–based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Nazari M, Oroojlooy A, Takáč M, Snyder LV (2018) Reinforcement learning for solving the vehicle routing problem. Proc. 32nd Internat. Conf. on Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 9861–9871.Google Scholar
• Neame PJ (1999) Nonsmooth dual methods in integer programming. Dissertation, University of Melbourne, Melbourne, Australia.Google Scholar
• Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, et al. (2011) Scikit-learn: Machine learning in Python. J. Machine Learn. Res. 12:2825–2830.Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.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
• Smith KA (1999) neural networks for combinatorial optimization: A review of more than a decade of research. INFORMS J. Comput. 11(1):15–34.Link, Google Scholar
• Václavík R, Novák A, Šůcha P, Hanzálek Z (2018) Accelerating the branch-and-price algorithm using machine learning. Eur. J. Oper. Res. 271(3):1055–1069.Crossref, Google Scholar
• Valério de Carvalho JM (2005) Using extra dual cuts to accelerate column generation. INFORMS J. Comput. 17(2):175–182.Link, 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
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, ed. Column Generation (Springer, New York), 331–358.Crossref, Google Scholar
• Wentges P (1997) Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2):151–162.Crossref, Google Scholar