Enhanced formulation for the Guillotine 2D Cutting Knapsack Problem

  • We advance the state of the art in Mixed-Integer Linear Programming formulations for Guillotine 2D Cutting Problems by (i) adapting a previously-known reduction to our preprocessing phase (plate-size normalization) and by (ii) enhancing a previous formulation (PP-G2KP from Furini et alli) by cutting down its size and symmetries. Our focus is the Guillotine 2D Knapsack Problem with orthogonal and unrestricted cuts, constrained demand, unlimited stages, and no rotation – however, the formulation may be adapted to many related problems. The code is available. Concerning the set of 59 instances used to benchmark the original formulation, the enhanced formulation takes about 4 hours to solve all instances while the original formulation takes 12 hours to solve 53 of them (the other six runs hit a three-hour time limit each). We integrate, to both formulations, a pricing framework proposed for the original formulation; the enhanced formulation keeps a significant advantage in this situation. Finally, in a recently proposed set of 80 harder instances, the enhanced formulation (with and without the pricing framework) found: 22 optimal solutions (5 already known, 17 new); better lower bounds for 25 instances; better upper bounds for 58 instances.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Henrique BeckerORCiD, Olinto AraújoORCiD, Luciana S. BuriolORCiD
DOI:https://doi.org/10.1007/s12532-022-00222-4
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2022
Volume:14
Issue:4
Page Number:25
First Page:673
Last Page:697
Mathematical Programming Computation :MPC 2022 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.