Back to Search
Start Over
A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing.
- Source :
- Mathematics of Operations Research; May2004, Vol. 29 Issue 2, p353-368, 16p, 8 Diagrams
- Publication Year :
- 2004
-
Abstract
- Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instance in two-or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0364765X
- Volume :
- 29
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Mathematics of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 13467113
- Full Text :
- https://doi.org/10.1287/moor.1030.0079