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

Language | English |
---|---|

Title of host publication | Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition |

Publisher | Wiley & Blackwell |

Pages | 107-129 |

Number of pages | 23 |

ISBN (Electronic) | 9781119005353 |

ISBN (Print) | 9781848216570 |

DOIs | |

Publication status | Published - 15 Sep 2014 |

### Fingerprint

### 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

*Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition*(pp. 107-129). Wiley & Blackwell. https://doi.org/10.1002/9781119005353.ch5

}

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

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-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 -