Two-Dimensional Bin Packing Problems

Andrea Lodi, Silvano Martello, Michele Monaci, Daniele Vigo

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

Fingerprint

Bin Packing Problem
Strip
Approximation Algorithms
Strip Packing
Lower bound
Packing Problem
Exact Algorithms
Metaheuristics
Heuristic algorithm
Approximate Solution
Optimal Solution
Mathematical Model
Upper bound
Minimise
Line
Evaluation
Family

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

Cite this

Lodi, A., Martello, S., Monaci, M., & Vigo, D. (2014). Two-Dimensional Bin Packing Problems. In Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition (pp. 107-129). Wiley & Blackwell. https://doi.org/10.1002/9781119005353.ch5
Lodi, Andrea ; Martello, Silvano ; Monaci, Michele ; Vigo, Daniele. / Two-Dimensional Bin Packing Problems. Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition. Wiley & Blackwell, 2014. pp. 107-129
@inbook{b2c89fa251f045a28a75b7c91496e689,
title = "Two-Dimensional Bin Packing Problems",
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.",
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",
author = "Andrea Lodi and Silvano Martello and Michele Monaci and Daniele Vigo",
year = "2014",
month = "9",
day = "15",
doi = "10.1002/9781119005353.ch5",
language = "English",
isbn = "9781848216570",
pages = "107--129",
booktitle = "Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition",
publisher = "Wiley & Blackwell",

}

Lodi, A, Martello, S, Monaci, M & Vigo, D 2014, Two-Dimensional Bin Packing Problems. in Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition. Wiley & Blackwell, pp. 107-129. https://doi.org/10.1002/9781119005353.ch5

Two-Dimensional Bin Packing Problems. / Lodi, Andrea; Martello, Silvano; Monaci, Michele; Vigo, Daniele.

Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition. Wiley & Blackwell, 2014. p. 107-129.

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

TY - CHAP

T1 - Two-Dimensional Bin Packing Problems

AU - Lodi, Andrea

AU - Martello, Silvano

AU - Monaci, Michele

AU - Vigo, Daniele

PY - 2014/9/15

Y1 - 2014/9/15

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Exact algorithms

KW - Lower bounds

KW - Metaheuristics

KW - Off-line heuristic algorithms

KW - One-phase algorithms

KW - Strip packing problem (2SP)

KW - Two-dimensional bin packing problem (2BP)

KW - Two-phase algorithms

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=84926484226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84926484226&partnerID=8YFLogxK

U2 - 10.1002/9781119005353.ch5

DO - 10.1002/9781119005353.ch5

M3 - Chapter

SN - 9781848216570

SP - 107

EP - 129

BT - Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition

PB - Wiley & Blackwell

ER -

Lodi A, Martello S, Monaci M, Vigo D. Two-Dimensional Bin Packing Problems. In Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition. Wiley & Blackwell. 2014. p. 107-129 https://doi.org/10.1002/9781119005353.ch5