Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming
Furini, Fabio; Malaguti, Enrico; Thomopulos, Dimitri (2016), Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming, INFORMS Journal on Computing, 28, 4, p. 736-751. 10.1287/ijoc.2016.0710
Type
Article accepté pour publication ou publiéDate
2016Journal name
INFORMS Journal on ComputingVolume
28Number
4Pages
736-751
Publication identifier
Metadata
Show full item recordAuthor(s)
Furini, FabioLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
Thomopulos, Dimitri
Abstract (EN)
We propose a framework to model general guillotine restrictions in two-dimensional cutting problems formulated as mixed-integer linear programs (MIPs). The modeling framework requires a pseudopolynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state-of-the-art MIP solver, can tackle instances of challenging size. We mainly concentrate our analysis on the guillotine two-dimensional knapsack problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. We also show how the modeling of general guillotine cuts can be extended to other relevant problems such as the guillotine two-dimensional cutting stock problem and the guillotine strip packing problem (GSPP). Finally, we conclude the paper discussing an extensive set of computational experiments on G2KP and GSPP benchmark instances from the literature.Subjects / Keywords
integer programming; guillotine cuts; mathematical modelRelated items
Showing items related by title and author.
-
Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié
-
Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano (2015) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico (2017) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence