EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1194. Solving Nesting Problems with Guillotine Cuts: A Novel Branch-and-Cut Algorithm

Invited abstract in session TB-29: Applications of combinatorial optimisation in industry and services II, stream Combinatorial Optimization.

Tuesday, 10:30-12:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. José Fernando Oliveira
INESC TEC, Faculty of Engineering, University of Porto
2. Luiz Henrique Cherri
Instituto de Ciências Matemáticas e de Computação, University of São Paulo
3. Adriana Cherri
Mathematics Department, UNESP, Bauru - INESC TEC, Portugal
4. Everton Fernandes da Silva
Computer Science, KU Leuven

Abstract

Cutting and packing problems have been studied for decades and the results of this research have a huge potential to improve many industrial production processes, both from an economic and environmental point of view. A widely studied problem is the two-dimensional irregular strip packing problem, aka nesting problem. This problem consists of placing a set of two-dimensional irregular polygonal pieces on a board with a fixed height and a length long enough to be considered infinite. The classical objective is to minimise the length of the board used to cut all the pieces. The two-dimensional irregular packing problem has been tackled by both heuristic and exact methods, allowing or not the rotation of the pieces. Despite the diversity of papers on this problem, there is a lack of research on the generation of cutting patterns that satisfy the constraints of guillotine cutting for irregular items, which is fundamental in the glass cutting industry, and only heuristic methods were proposed to solve two-dimensional irregular cutting and packing problems with guillotine cuts. We will present an innovative branch-and-cut method to represent and exactly solve all variants of irregular cutting and packing problems with guillotine cuts that deal with a single board (aka as bin, plate or strip), namely the irregular strip packing problem, the irregular placement problem, the irregular knapsack problem, and the irregular identical item problem.

Keywords

Status: accepted

Back to the list of papers