Please use this identifier to cite or link to this item:
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKönig, Felix G.
dc.contributor.authorLübbecke, Marco E.
dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorSchäfer, Guido
dc.contributor.authorSpenke, Ines
dc.description.abstractWe 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.en
dc.subject.ddc510 Mathematiken
dc.subject.othernondeterministic constraint logicen
dc.subject.otherrollout algorithmsen
dc.subject.otherreal-world applicationen
dc.titleSolutions to Real-World Instances of PSPACE-Complete Stackingen
dc.typeResearch Paperen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2007, 04en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 185.52 kB
DownloadShow Preview
Format: Postscript | Size: 397.69 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.