Computing at Glasgow University
Paper ID: 8069

A Constraint model and a reduction operator for the minimising open stacks problem
Miller,A. Prosser,P. Unsworth,C.

Publication Type: Conference Proceedings
Appeared in: Proceedings of the constraint modelling challenge, in conjuction with the fifth workshop on modelling and solving problems with constraints held at IJCAI'05
Page Numbers : 44-50
Publisher: N/A
Year: 2005

We present two constraint models for the minimising open stacks problem (MOSP). Our first model is based on that reported in [Gregory, Miller and Prosser 2004], and our second is a refinement and is more space efficient. We also present two reduction operators for the MOSP. One reduction operator is applied as a pre-process to remove elements of the problem that are provably redundant, the second dynamically reduces the problem during search. We also introduce conditional lower bounds, which are lower bounds associated with a partial assignment. Experiments are then performed using the two reduction operators, and our best constraint model using the lower bounds reported in [Miller 2005] and the conditional lower bounds.

Keywords: Minimising open stacks problem, constraint programming, reduction operator

PDF Bibtex entry Endnote XML