Wallace, Richard J. (University College Cork)

Neighbourhood singleton arc consistency (NSAC) is a type of singleton arc consistency (SAC) in which the subproblem formed by variables adjacent to a variable with a singleton domain is made arc consistent. In this paper we consider how to apply this form of consistency reasoningto problems with n-ary constraints including global constraints. The chief problem encountered is that of neighbouring variables contained in a constraint that also includes non-neighbouring variables. In this case, a strict extension of NSAC involves projection of such constraints onto the neighbourhood variables, but for many global constraints this may be difficult to do in practice. Here, we consider a simple variant called restricted neighbourhood SAC, that avoids this problem. We compare the two approaches on random and structured problems and show that in all cases the restricted form of k-NSAC is nearly as effective as the unrestricted form.

Wallace, Richard J. (University College Cork) | Grimes, Diarmuid (University College Cork) | Freuder, Eugene C. (University College Cork)

This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) with finite domains and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action as well as overall quality of search. In addition, classical DCSP methods perform poorly on these problems because there are sometimes no solutions similar to the original one found. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique for iterated sampling that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions.

Using information from failures to guide subsequent search is an important technique for solving combinatorial problems in domains such as boolean satisfiability (SAT) and constraint satisfaction problems (CSPs). The information learnt can take various forms such as fine-grained information in the form of no-goods and explanations in CSPs and clause learning in SAT, or coarse-grained information in the form of constraint weighting in CSPs and clause weighting in SAT. In this paper we focus on CSPs, using constraint weighting with restarts in order to identify global bottlenecks in a problem. This information is then used by a "weighted-degree" heuristic to guide complete search, with the belief that instantiating these elements first will reduce the overall search effort required to either find a solution or prove the problem insoluble. We introduce two restarting strategies.

Wallace, Richard J. (University College Cork)

Algorithms based on the general idea of singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. It is shown that, using the proper procedures, partial (N)SAC is associated with a unique fixpoint for any given subset of variables. Various heuristic strategies for choosing the designated subset are described and tested, in particular a strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as full (N)SAC in terms of values discarded while greatly reducing the effort required.