We study pseudopolynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudopolynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models. We propose upper- and lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions.

Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems / Delorme, Maxence; Iori, Manuel. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 32:1(2020), pp. 101-119. [10.1287/ijoc.2018.0880]

Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems

Manuel Iori
2020

Abstract

We study pseudopolynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudopolynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models. We propose upper- and lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions.
18-lug-2019
32
1
101
119
Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems / Delorme, Maxence; Iori, Manuel. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 32:1(2020), pp. 101-119. [10.1287/ijoc.2018.0880]
Delorme, Maxence; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
6270.pdf

accesso aperto

Descrizione: Versione pre print
Tipologia: Pre-print dell'autore (bozza pre referaggio)
Dimensione 376.01 kB
Formato Adobe PDF
376.01 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1174547
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 25
social impact