Optimization Online


Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming

Fabio Furini (fabio.furini***at***dauphine.fr)
Enrico Malaguti (enrico.malaguti***at***unibo.it)
Dimitri Thomopulos (dimitri.thomopulos***at***unibo.it)

Abstract: We propose a framework to model general guillotine restrictions in two-dimensional cutting problems formulated as Mixed Integer Linear Programs (MIP). The modeling framework requires a pseudo-polynomial 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 (G2CSP) 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.


Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 11/25/2014
Entry Accepted: 11/25/2014
Entry Last Modified: 02/11/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society