×

zbMATH — the first resource for mathematics

Higher-dimensional packing with order constraints. (English) Zbl 1018.90035
Dehne, Frank (ed.) et al., Algorithms and data structures. 7th international workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2125, 300-312 (2001).
Summary: We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as higher-dimensional generalizations of scheduling problems. Using graph-theoretic structures to describe feasible solutions, we develop a novel exact branch-and-bound algorithm. This extends previous work by Fekete and Schepers; a key tool is a new order-theoretic characterization of feasible extensions of a partial order to a given comparability graph that is tailor-made for use in a branch-and-bound environment. The usefulness of our approach is validated by computational results.
For the entire collection see [Zbl 0969.00079].

MSC:
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: Link