An Exact Approach to the Strip-Packing Problem

Silvano Martello, Michele Monaci, Daniele Vigo

INFORMS Journal on Computing · 2003 · Volume 15 · Issue 3

Abstract

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items.

Keywords

Cutting, Packing, Branch and Bound, Relaxations, Algorithms

Enable JavaScript for citation tools and additional paper interactions.