Higher-Dimensional Packing with Order Constraints

Details Higher-Dimensional Packing with Order Constraints Higher-Dimensional Packing with Order Constraints

2003-08-04

arxiv.org/abs/cs/0308006v2

Computer Science

Data Structures and Algorithms

23 pages, 14 figures, 5 tables, Latex; revision clarifies various minor points, fixes typos, etc. To appear in SIAM Journal on

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Higher-Dimensional Packing with Order Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Higher-Dimensional Packing with Order Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Higher-Dimensional Packing with Order Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176392