1571. A Deep Reinforcement Learning-based column generation for the 2D bounded-sized cutting stock problem
Invited abstract in session MB-21: 2D Cutting and Packing, stream Cutting and packing (ESICUP).
Monday, 10:30-12:00Room: Esther Simpson 2.12
Authors (first author is the speaker)
| 1. | Alexis Robbes
|
| Université de Technologie de Troyes | |
| 2. | Khadija Alice HADJ SALEM
|
| NUMA, KU Leuven |
Abstract
In this work, we propose a Deep Reinforcement Learning-based column generation approach to solve the two-dimensional bounded-sized cutting stock problem (2D-BSCSP). The 2D-BSCSP is a variant of the 2D cutting stock problem in which the dimensions of the raw material plates are variables, constrained to fall within a specific range. This introduces additional complexity, as the dimensions of the plates are not fixed and must be considered when optimizing the cutting process. The cutting procedure involves two non-exact guillotine stages. We begin by introducing a new Mixed-Integer Linear Programming (MILP) formulation based on strip-based representations. Building on this, we present a column generation method that combines a Deep Q-Learning algorithm with a dynamic programming algorithm and MILP models. The Deep Q-Learning algorithm enables the method to learn the profit of the items over time, while dynamic programming is used to generate strips based on these profits. The proposed method is trained on a set of randomly generated instances, which serve as a diverse representation of possible problem scenarios. To assess its performance and generalizability, the method is validated on adapted 2D-Cutting Stock Problem (2D-CSP) instances from existing literature. These instances provide a benchmark to evaluate the effectiveness of our approach in solving real-world cutting stock problems. Finally, we compare the results of our DRL-based column generation method with those of an
Keywords
- Cutting and Packing
- Column Generation
- Artificial Intelligence
Status: accepted
Back to the list of papers