A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
Authors:
- 1 May 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 29 (2) , 353-368
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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A General Framework for Bounds for Higher-Dimensional Orthogonal Packing ProblemsMathematical Methods of Operations Research, 2004
- Packing small boxes into a big boxMathematical Methods of Operations Research, 2000
- RECTANGLE AND BOX VISIBILITY GRAPHS IN 3DInternational Journal of Computational Geometry & Applications, 1999
- An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problemsEuropean Journal of Operational Research, 1995
- An exact algorithm for general, orthogonal, two-dimensional knapsack problemsEuropean Journal of Operational Research, 1995
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- An Incremental Linear-Time Algorithm for Recognizing Interval GraphsSIAM Journal on Computing, 1989
- An exact algorithm for the pallet loading problemEuropean Journal of Operational Research, 1987
- Network flows and non-guillotine cutting patternsEuropean Journal of Operational Research, 1984
- A Characterization of Comparability Graphs and of Interval GraphsCanadian Journal of Mathematics, 1964