Max-CSP competition 2008: toulbar2 solver description
Martí Sánchez-Fibla, Sylvain Bouveret, Simon de Givry, Federico Heras, Javier Larrosa, Samba Ndiaye, Emma Rollón, Thomas Schiex, Cyril Terrioux, Gérard Verfaillie, Matthias Zytnicki · 2008
This document presents the key techniques used in toulbar2 solver submitted to the Max-CSP competition 2008. toulbar2 solves Weighted Con- straint Satisfaction Problems (WCSPs), a generalisation of Max-CSP. Two com- plete solving methods that have been used for the competition are presented in this paper: Depth-First Branch and Bound (DFBB) and a new algorithm, Russian Doll Search with tree decomposition (RDS-BTD), which exploits the problem structure. DFBB is commonly used to solve constraint optimization problems such as WC- SPs. The worst-case time complexity of this algorithm can be improved by ex- ploiting the constraint graph structure, identifying independent subproblems and caching their optima. However, the exploitation of the structure is done a poste- riori : each time a new subproblem occurs, it has to be solved before its optimum can be used. RDS-BTD solves a relaxation of every subproblem before solving the whole problem, in the spirit of the Russian Doll Search algorithm. This relax- ation allows to exploit subproblem lower bounds in a more proactive way.