A combinatorial characterization of higher-dimensional orthogonal packing

• 成果类型: Article
• 署名作者: Fekete, SP; Schepers, J
• 署名单位: Braunschweig University of Technology; International Business Machines (IBM); IBM Germany
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1030.0079
• 发表日期: 2004
• 页码: 353-368
• 关键词: exact algorithm; graphs

摘要

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.