Practical tractability of CSPs by higher level consistency and tree decomposition.

摘要

Constraint Satisfaction is a flexible paradigm for modeling many decision problems in Engineering, Computer Science, and Management. Constraint Satisfaction Problems (CSPs) are in general $NP$-complete and are usually solved with search. Research has identified various islands of tractability, which enable solving certain CSPs with backtrack-free search. For example, one sufficient condition for tractability relates the consistency level of a CSP to treewidth of the CSP's constraint network. However, enforcing higher levels of consistency on a CSP may require the addition of constraints, thus altering the topology of the constraint network and increasing its treewidth. This thesis addresses the following question: How close can we approach in practice the tractability guaranteed by the relationship between the level of consistency in a CSP and the treewidth of its constraint network?;To achieve "practical tractability," this thesis proposes: (1) New local consistency properties and algorithms for enforcing them without adding constraints or altering the network's topology; (2) Methods to enforce these consistency properties on the clusters of a tree decomposition of the CSP; and (3) Schemes to bolster the propagation between the clusters of the tree decomposition.;Our empirical evaluation shows that our techniques allow us to achieve practical tractability for a wide range of problems, and that they are both applicable (i.e., require acceptable time and space) and useful (i.e., outperform other consistency properties). We theoretically characterize the proposed consistency properties and empirically evaluate our techniques on benchmark problems. Our techniques for higher level consistency exhibit their best performances on difficult benchmark problems. They solve a larger number of difficult problem instances than algorithms enforcing weaker consistency properties, and moreover they solve them in an almost backtrack-free manner.