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

Sebastian Kraul, Markus Seizinger, Jens O. Brunner

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)692-709
Number of pages18
JournalINFORMS Journal on Computing
Volume35
Issue number3
Early online date29 Mar 2023
DOIs
Publication statusPublished - Jun 2023

Fingerprint

Dive into the research topics of 'Machine Learning–Supported Prediction of Dual Variables for the Cutting Stock Problem with an Application in Stabilized Column Generation'. Together they form a unique fingerprint.

Cite this