Optimization Online


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

Maxence Delorme(maxence.delorme2***at***unibo.it)
Manuel Iori(manuel.iori***at***unimore.it)

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 less 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 non-trivial 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 upon previous algorithms and finding several new proven optimal solutions.

Keywords: bin packing, cutting stock, pseudo-polynomial, equivalent models, variable size, fragmentation

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: M. Delorme and M Iori. Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. Technical report OR-17-6, DEI “Guglielmo Marconi”, Alma Mater Studiorum Università di Bologna, Italy, 2017.

Download: [PDF]

Entry Submitted: 10/13/2017
Entry Accepted: 10/13/2017
Entry Last Modified: 10/13/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society