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

Sebastian Kraul (), Markus Seizinger () and Jens O. Brunner ()
Additional contact information
Sebastian Kraul: Department of Operations Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Markus Seizinger: Health Care Operations/Health Informations Management, University of Augsburg, 86159 Augsburg, Germany
Jens O. Brunner: Health Care Operations/Health Informations Management, University of Augsburg, 86159 Augsburg, Germany; Department of Technology, Management, and Economics, Technical University of Denmark, DK-2800 Kongens Lyngby, Denmark

INFORMS Journal on Computing, 2023, vol. 35, issue 3, 692-709

Abstract: This article presents a prediction model of the optimal dual variables for the cutting stock problem. For this purpose, we first analyze the influence of different attributes on the optimal dual variables within an instance for the cutting stock problem. We apply and compare our predictions in a stabilization technique for column generation. In most studies, the parameters for stabilized column generation are determined by numerical tests, that is, the same problem is solved several times with different settings. We develop two learning algorithms that predict the best algorithm configuration based on the predicted optimal dual variables and thus omit the numerical study. Our extensive computational study shows the tradeoff between the learning algorithms using full and sparse instance information. We show that both algorithms can efficiently predict the optimal dual variables and dominate the common update mechanism in a generic stabilized column generation approach. Although the learning algorithm with full instance information is applicable when one has to solve the problem mainly for a fixed set of items, the algorithm with sparse instance information is applicable when there is more variability in the number of items between the different instances.

Keywords: cutting stock problem; machine learning; stabilized column generation; parameter optimization; duality (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1277 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:3:p:692-709

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().