Higher-Dimensional Packing with Order Constraints
<|reference_start|>Higher-Dimensional Packing with Order Constraints: 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 complementarity graph that is tailor-made for use in a branch-and-bound environment. The usefulness of our approach is validated by computational results.<|reference_end|>
@article{fekete2003higher-dimensional,
    title={Higher-Dimensional Packing with Order Constraints},
    author={Sandor P. Fekete and Ekkehard Koehler and Juergen Teich},
    journal={arXiv preprint arXiv:cs/0308006},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0308006},
    primaryClass={cs.DS cs.DM}
}