• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2016
Journal name
INFORMS Journal on Computing
Volume
28
Number
4
Pages
736-751
Publication identifier
10.1287/ijoc.2016.0710
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire 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 model

Related items

Showing items related by title and author.

  • Thumbnail
    On integer and bilevel formulations for the k-vertex cut problem 
    Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié
  • Thumbnail
    Automatic Dantzig–Wolfe reformulation of mixed integer programs 
    Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano (2015) Article accepté pour publication ou publié
  • Thumbnail
    Solving vertex coloring problems as maximum weight stable set problems 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico (2017) Article accepté pour publication ou publié
  • Thumbnail
    The vertex k-cut problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    Mathematical formulations for the Balanced Vertex k-Separator Problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo