Learning from the past to dynamically improve search: a case study on the MOSP problem
Hadrien Cambazard, Narendra Jussien · 2008
Abstract. This paper presents a study conducted on the min-imum number of open stacks problem (MOSP) which occurs in various production environments where an efficient simultane-ous utilization of resources (stacks) is needed to achieve a set of tasks. We investigate through this problem how classical look-back reasonings based on explanations could be used to prune the search space and design a new solving technique. Explana-tions have often been used to design intelligent backtracking mechanisms in Constraint Programming whereas their use in nogood recording schemes has been less investigated. In this pa-per, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving tech-nique and can provide explanations. 1 The Minimum number of Open Stacks Problem The Minimum number of Open Stacks Problem (MOSP) has been recently used