Mathematical Models and Decomposition Algorithms for Cutting and Packing Problems

Delorme, Maxence (2017) Mathematical Models and Decomposition Algorithms for Cutting and Packing Problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Automatica e ricerca operativa, 29 Ciclo. DOI 10.6092/unibo/amsdottorato/7828.
Documenti full-text disponibili:
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato.
Download (1MB) | Anteprima


In this thesis, we provide (or review) new and effective algorithms based on Mixed-Integer Linear Programming (MILP) models and/or decomposition approaches to solve exactly various cutting and packing problems. The first three contributions deal with the classical bin packing and cutting stock problems. First, we propose a survey on the problems, in which we review more than 150 references, implement and computationally test the most common methods used to solve the problems (including branch-and-price, constraint programming (CP) and MILP), and we successfully propose new instances that are difficult to solve in practice. Then, we introduce the BPPLIB, a collection of codes, benchmarks, and links for the two problems. Finally, we study in details the main MILP formulations that have been proposed for the problems, we provide a clear picture of the dominance and equivalence relations that exist among them, and we introduce reflect, a new pseudo-polynomial formulation that achieves state of the art results for both problems and some variants. The following three contributions deal with two-dimensional packing problems. First, we propose a method using Logic based Benders’ decomposition for the orthogonal stock cutting problem and some extensions. We solve the master problem through an MILP model while CP is used to solve the slave problem. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. Then, we introduce TwoBinGame, a visual application we developed for students to interactively solve two-dimensional packing problems, and analyze the results obtained by 200 students. Finally, we study a complex optimization problem that originates from the packaging industry, which combines cutting and scheduling decisions. For its solution, we propose mathematical models and heuristic algorithms that involve a non-trivial decomposition method. In the last contribution, we study and strengthen various MILP and CP approaches for three project scheduling problems.

Tipologia del documento
Tesi di dottorato
Delorme, Maxence
Dottorato di ricerca
Settore disciplinare
Settore concorsuale
Parole chiave
Combinatorial optimization, Cutting and Packing, Bin packing, Cutting stock, Orthogonal packing, Project scheduling, Exact algorithms, Pseudo-polynomial formulation, Computational evaluation
Data di discussione
5 Aprile 2017

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi