Solutions to Real-World Instances of PSPACE-Complete Stacking

Felix G. König, Marco E. Lübbecke, Rolf H. Möhring, Guido Schäfer, and Ines Spenke

Algorithms - ESA 2007: 15th Annual European Symposium, volume 4698 of Lecture Notes in Computer Science, pp. 729-740, Springer, 2007.

not available

stack, PSPACE-complete, nondeterministic constraint logic, rollout algorithms, real-world application

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.

Download as [PDF] [ps]