Two-Dimensional Bin Packing Problems

Andrea Lodi*, Silvano Martello, Michele Monaci, Daniele Vigo

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

Abstract

An important variant of two-dimensional bin packing problem (2BP), which is also used in some approximation algorithms for its solution, is the strip packing problem (2SP), in which the items have to be packed in a strip of width W and infinite height, so as to minimize the height at which the strip is used. This chapter starts by reviewing classical mathematical models which have implications relevant to the topic of the present survey, and discuss more recent results. It devotes to upper bounds; including metaheuristics and approximation algorithms, lower bound, and exact algorithms. Most of the off-line heuristic algorithms from the literature are of the greedy type, and can be classified in two families: one-phase algorithms and two-phase algorithms. Good lower bounds on the optimal solution value are important both in the implementation of exact enumerative approaches and in the empirical evaluation of approximate solutions.

Original languageEnglish
Title of host publicationParadigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition
PublisherWiley & Blackwell
Pages107-129
Number of pages23
ISBN (Electronic)9781119005353
ISBN (Print)9781848216570
DOIs
Publication statusPublished - 15 Sep 2014

Keywords

  • Approximation algorithms
  • Exact algorithms
  • Lower bounds
  • Metaheuristics
  • Off-line heuristic algorithms
  • One-phase algorithms
  • Strip packing problem (2SP)
  • Two-dimensional bin packing problem (2BP)
  • Two-phase algorithms
  • Upper bounds

Fingerprint Dive into the research topics of 'Two-Dimensional Bin Packing Problems'. Together they form a unique fingerprint.

Cite this