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

International audienceIn this paper, we are interested in enumerative resolution methods for combinatorial optimization (COP) and constraint satisfaction problems (CSP). We introduce a new approch for the management of branching, called Dynamic Cooperative Search (DCS) inspired from the impact-based search method proposed in Refalo (2004) 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 Refalo (2004), 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