Contributions to search and inference algoriths for CSP and weighted CSP

Author: Martí Sánchez
University: Universitat Politècnica de Catalunya
Advisor: Javier Larrosa, Pedro Meseguer
Year: 2006

This thesis presents a collection of new algorithms for solving Constraint Satisfaction Problems (CSP) and Weighted Constraint Satisfaction Problems (WCSP).We pursue two main objectives: enhancing solving methods for WCSP, which are of recent development, and narrowing the gap between search and inference methods. The first part of the thesis is devoted to search methods for solving WCSP. In a branch-and-bound context, the lower bound computation in each node of the search is of great importance and has a serious impact in the practical efficiency of algorithms. We start from an algorithm called Russian Doll Search (RDS) that has a costly, yet very powerful lower bound and we develop three enhancements of it: Specialized RDS (SRDS), Full SRDS and Opportunistic SRDS [Meseguer and Sanchez, 2001] [Meseguer et al.2002]. We then tackle the problem of exploiting the global structure of the problem inside search. An algorithm exists for CSP that is able to exploit what is called pseudo-tree structure extend it to WCSP, obtaining algorithm Pseudo Tree Partial Forward Checking (PT-PFC). This algorithm has a source of inefficiency mainly related to bad quality local lower and upper bounds. We suggest a solution to this problem by combining pseudo-tree search for WCSP with the RDS techniques that we previously developed obtaining algorithms PT-RDS and PT-SRDS [?] [Larrosa et al., 2002]. In all this first part the aim is enhancing the practical efficiency of existing search algorithms with respect to the time spent in solving several benchmarks. The second part of the thesis is devoted to complete inference methods for solving CSP and WCSP. Complete inference solves the problem by a sequence of transformations that obtain an equivalent problem. In these transformations variable elimination plays an important role. We present some new inference operations that permit us to factorize a constraint into a set of smaller size constraints. We then introduce factorization into variable elimination. The result is algorithm Adaptive Consistency with negative factorized constraints (ADC?factor) [Sanchez et al., 2004b]. With these operations we define also an alternative method to eliminate a binary domain variable. Next, we introduce the idea of Filtering which consists in anticipating tuples of constraints that will become inconsistent when joined with other constraints of the problem. One could say that we are doing the equivalent to look-ahead during search but the goal is to reduce memory storage instead of pruning branches and reduce time. We introduce filtering in the main complete inference algorithms for CSP and WCSP producing Delayed Variable Elimination with Filtering ADC (ADC-DVE-F) [Sanchez et al., 2004a] [Sanchez et al., 2005a] and Bucket Elimination-DVE-F algorithms. Still in the complete inference context, we generalize filtering to tree decomposition methods that yield us to Cluster Tree Elimination CTE-F algorithm. We also present an iterative pure inference algorithm that performs a sequence of more accurate approximations to solve the problem, we call it Iterative Mini Cluster Tree Elimination (IMCTE) [Sanchez et al., 2005b]. All contributions to the complete inference part of the thesis are devoted to enhance the memory spent by these methods.