Extending to Soft and Preference Constraints a Framework for Solving Efficiently Structured Problems

Contents

This paper deals with the problem of solving efficiently structured COPs (Constraints Optimization Problems). The formalism based on COPs allows to represent numerous real-life problems defined using constraints and to manage preferences and soft constraints. In spite of theoretical results, cite{JNT07b} has discarded (hyper)tree-decompositions for the benefit of coverings by acyclic hypergraphs in the CSP area. We extend here this work to constraint optimization. We first study these coverings from a theoretical viewpoint. Then we exploit them in a framework aiming not to define a new decomposition, but to make easier a dynamic management of the structure during the search (unlike most of structural methods which usually exploit the structure statically), and so the use of dynamic variable ordering heuristics. Thus, we provide a new complexity result which outperforms significantly the previous one given in the literature. Finally, we assess the practical interest of these notions.