EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1168. Solving the two dimensional strip packing problem using reinforcement learning framework

Invited abstract in session WB-28: Advancements of OR-analytics in statistics, machine learning and data science 9, stream Advancements of OR-analytics in statistics, machine learning and data science.

Wednesday, 10:30-12:00
Room: 065 (building: 208)

Authors (first author is the speaker)

1. Fatih Burak Akcay
Econometrics and Operations Research, Tilburg University
2. Maxence Delorme
Tilburg University

Abstract

In the 2D Strip Packing Problem (SPP), the objective is to pack items into a fixed-width strip, minimizing the height of the packing. A common approach to solving the SPP efficiently is through decomposition algorithms, which split the problem into primary and secondary subproblems. The primary problem involves solving a relaxed version of the SPP, like the one-dimensional contiguous bin packing problem or parallel processor scheduling problem with contiguity constraints. Using a feasible solution from the primary problem, the secondary problem constructs a valid SPP solution. If none is found, techniques such as adding a cut or banning the current solution are applied. Various formulations, including integer linear programming models or constraint programming models, exist for the primary problem. Empirical evidence suggests that different solution approaches perform better for different instances, with no single dominating formulation. Our research focuses on developing automated hyper-algorithms capable of selecting the most appropriate method or sequence of methods for solving a given instance, following the trend of integrating machine learning techniques into optimization algorithms. We utilize reinforcement learning to determine which mathematical model to employ in the primary problem, along with other features for incorporation into the decomposition scheme. The proposed framework's performance is evaluated using benchmark datasets.

Keywords

Status: accepted

Back to the list of papers