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
-
-
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
-
