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

Maxence Delorme, Manuel Iori

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

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- A nd 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. Â

Original languageEnglish
Pages (from-to)101-119
Number of pages19
JournalINFORMS Journal on Computing
Volume32
Issue number1
DOIs
Publication statusPublished - Mar 2020
Externally publishedYes

Keywords

  • Bin packing
  • cutting stock
  • equivalent models
  • fragmentation
  • pseudo-polynomial
  • variable size

Fingerprint Dive into the research topics of 'Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems'. Together they form a unique fingerprint.

Cite this