Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems

Maxence Delorme () and Manuel Iori ()
Additional contact information
Maxence Delorme: School of Mathematics, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom
Manuel Iori: Dipartimento di Scienze e Metodi dell'Ingegneria (DISMI), Università di Modena e Reggio Emilia, 42122 Reggio Emilia, Italy

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 101-119

Abstract: We study pseudo-polynomial 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 pseudo-polynomial 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.

Keywords: bin packing; cutting stock; pseudo-polynomial; equivalent models; variable size; fragmentation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0880 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:101-119

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().