Solving the Minimum Number of Open Stacks Problem with Explanation-based Techniques.
Hadrien Cambazard, Narendra Jussien · 2007
This paper presents a study conducted on the minimum number of open stacks problem (MOSP) which occurs in various production environments where an efficient simultaneous 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. Explanations have often been used to design intelligent backtrack-ing mechanisms in Constraint Programming whereas their use in nogood recording schemes has been less in-vestigated. In this paper, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving technique and can provide explanations.