Recording and Minimising Nogoods from Restarts in the Solver MiniCP

Sammanfattning

Systematic search is a typical search algorithm in Constraint Programming. The solving performance of this search algorithm is affected by the heavy-tailed phenomenon, which can cause search to spend significant time exploring subtrees that contain no solutions to the problem instance. Search using restarts, and recording and exploitation of nogoods, called nogoods search, is a search algorithm that is designed to guard against the heavy-tailed phenomenon. Results from previous research suggest that nogoods search does this well, significantly improving the solving performance for some problems. What is not indicated by previous research is to what degree randomisation affects the results. Two runs of solving the same problem instance may have vastly different solving times, therefore it would not be fair to compare two search algorithms on the same problem instance unless we can ensure that both runs are made under the exact same circumstances. The concept of storing and replaying a search tree introduces the possibility to store a search tree when solving a problem instance, and then replay the search tree for any repeated runs. This allows us to compare search algorithms in a controlled environment where the circumstances are kept constant. This thesis project implements nogoods search, and store and replay in the educational Constraint Programming solver called MiniCP, allowing for future research and studies to made on the topic. Experimental results show that nogoods search in a controlled environment can outperform systematic search in some problems. However, it is also indicated that the performance of nogoods search heavily relies on the order of which variables and values are selected for exploration during search, which can dictate whether nogoods search either is up one order of a magnitude faster than systematic search, or at least twice as slow.