Solutions to Real-World Instances of PSPACE-Complete Stacking
| Autor: | Guido Schäfer, Marco E. Lübbecke, Rolf H. Möhring, Ines Spenke, Felix G. König |
|---|---|
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Algorithms – ESA 2007 ISBN: 9783540755197 ESA |
| DOI: | 10.1007/978-3-540-75520-3_64 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|