Dynamic Cooperative Search for constraint satisfaction and combinatorial optimization: application to a rostering problem

In this paper, we are interested in enumerative resolution methods for combinatorial optimiza-tion (COP) and constraint satisfaction problems (CSP). We introduce a new approch for the man-agement of branching, called Dynamic Cooperative Search (DCS) inspired from the impact-based search method proposed in [7] for CSPs. This method defines in a dynamic way priority rules for variable and value selection in the branching scheme. These rules are meant to be independent of the considered problem. As in [7], the principle is to take into account, through learning methods, of the impact of branching decisions in already explored subparts of the search tree. We show the interest of DCS on a real-life rostering problem. 1 Dynamic Cooperative Search: principle and first results Most of the exact resolution methods for combinatorial optimization (COP) and constraint satis-faction problems (CSP), such as tree search, branch and bound and dynamic programming, rely on an intelligent enumeration of the solutions. In tree search methods, used for the resolution of both CSPs and COPs, child generation (or branching) consists in selecting a variable and its tentative value. In many cases, the branching policy, i.e., the strategy for the variable and value selections, have a huge influence on the efficiency of the method. In the case where the strategy allows on