Minimizing the maximum number of open stacks by customer search

Geoffrey Chu, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

23 Citations (Scopus)


We describe a new exact solver for the minimization of open stacks problem (MOSP). By combining nogood recording with a branch and bound strategy based on choosing which customer stack to close next, our solver is able to solve hard instances of MOSP some 5-6 orders of magnitude faster than the previous state of the art. We also derive several pruning schemes based on dominance relations which provide another 1-2 orders of magnitude improvement. One of these pruning schemes largely subsumes the effect of the nogood recording. This allows us to reduce the memory usage from an potentially exponential amount to a constant ~2Mb for even the largest solvable instances. We also show how relaxation techniques can be used to speed up the proof of optimality by up to another 3-4 orders of magnitude on the hardest instances.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
Number of pages16
ISBN (Print)3642042430, 9783642042430
Publication statusPublished - 2 Nov 2009
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2009 - Lisbon, Portugal
Duration: 22 Sep 200924 Sep 2009
Conference number: 15th (Conference Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5732 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2009
Abbreviated titleCP 2009
Internet address

Cite this