Inhalt des Dokuments
Preprint 04-2007
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Solutions to Real-World Instances of PSPACE-Complete Stacking
- Authors
- Publication
- Algorithms - ESA 2007: 15th Annual European Symposium, volume 4698 of Lecture Notes in Computer Science, pp. 729-740, Springer, 2007.
- Classification
-
not available
- Keywords
-
stack, PSPACE-complete, nondeterministic constraint logic, rollout algorithms, real-world application
- Abstract
-
We investigate a complex stacking problem that stems from storage planning of steel slabs in integrated steel production. Besides the practical importance of such stacking tasks, they are appealing from a theoretical point of view. We show that already a simple version of our stacking problem is PSPACE-complete. Thus, fast algorithms for computing provably good solutions as they are required for practical purposes raise various algorithmic challenges. We describe an algorithm that computes solutions within 5/4 of optimality for all our real-world test instances. The basic idea is a search in an exponential state space that is guided by a state-valuation function. The algorithm is extremely fast and solves practical instances within a few seconds. We assess the quality of our solutions by computing instance-dependent lower bounds from a combinatorial relaxation formulated as mixed integer program. To the best of our knowledge, this is the first approach that provides quality guarantees for such problems.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe