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.

Modeling two-dimensional guillotine cutting problems via integer programming

Thomopulos, Dimitri
2016-01-01

Abstract

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.
2016
Furini, Fabio; Malaguti, Enrico; Thomopulos, Dimitri
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/956785
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 39
social impact