Eliciting Sub-problem Equivalence Candidates for CP Models

This paper presents a method that, given a constraint problem model, automatically constructs relatively simple run-time conditions likely to ensure the equivalence of any two sub-problems that satisfy them. When proved correct, these conditions can be used by a caching search to improve efficiency. Note that our method deals with constraint problem models, rather than with single instances, thus considerably reducing its overhead and increasing its accuracy. While we do not yet have an automatic method to prove the proposed conditions are correct (that is why we talk about candidates for sub-problem equivalence), our preliminary results indicate the candidates proposed are easy to prove manually and can indeed yield significant reductions in search effort.