Search

CP solvers predominantly use arc consistency (AC) as the default propagation method for binary constraints. Many stronger consistencies, such as triangle consistencies (e.g. RPC and maxRPC) exist, but their use is limited despite results showing that they outperform AC on many problems. This is due to the intricacies involved in incorporating them into solvers. On the other hand, singleton consistencies such as SAC can be easily crafted into solvers but they are too expensive in practice. Seeking a balance between the efficiency of triangle consistencies and the ease of implementation of singleton ones, we study the family of neighborhood singleton consistencies (NSCs) which extends the recently proposed neighborhood SAC (NSAC). We propose several new members of this family and study them both theoretically and experimentally. Our theroretical results show that the pruning power of the proposed NSCs ranges between that of RPC and (3,1)-consistency. Using a very simple algorithm for the implementation of NSCs, we demonstrate that certain members of the NSC family are quite competitive as general-purpose propagation methods for binary constraints, significantly outperforming the existing propagation techniques on some problem classes.

Restricted path consistency (RPC) is a strong local consistency for binary constraints that was proposed 20 years ago and was identified as a promising alternative to arc consistency (AC) in an early experimental study of local consistencies for binary constraints. However, in contrast to other strong local consistencies such as singleton arc consistency (SAC) and max restricted path consistency (maxRPC), it has been neglected since then. In this paper we revisit RPC. First we propose RPC3, a new RPC algorithm that is very easy to implement and can be efficiently applied throughout search. Then we perform a wide experimental study of RPC3 and a light version that achieves an approximation of RPC, comparing them to state-of-the-art AC and maxRPC algorithms. Experimental results obtained under various solver settings, regarding the branching scheme, the variable ordering heuristic, and restarts, clearly show that light RPC is by far more efficient than both AC and maxRPC when applied throughout search. We also examine the experimental behaviour of an algorithm for a simple extension of RCP called 2-RPC, showing that it is competitive with RPC3, and better than both AC and maxRPC. Overall, our results strongly suggest that it is time to reconsider the established perception that MAC is the best general purpose method for solving binary CSPs.

International audience; Table constraints are important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose new filtering algo- rithms for positive table constraints that achieve stronger local consistency proper- ties than GAC by exploiting intersections between constraints. The first algorithm, called maxRPWC+, is a domain filtering algorithm that is based on the local con- sistency maxRPWC and extends the GAC algorithm of Lecoutre and Szymanek [23]. The second algorithm extends the state-of-the-art STR-based algorithms to stronger relation filtering consistencies, i.e., consistencies that can remove tu- ples from constraints’ relations. Experimental results from benchmark problems demonstrate that the proposed algorithms are quite competitive with standard GAC algorithms like STR2 in some classes of problems with intersecting table con- straints, being orders of magnitude faster in some cases.

Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end 3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one, maxRPC3 rm , has O(en 2 d 4) time complexity, but a restricted version with O(end 4) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3 rm . All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a viable alternative to arc consistency on some problem classes.

Constraint satisfaction problems (CSPs) and satisfiability problem (SAT) are very successful frameworks that are used to model and solve a wide variety of combinatorial problems. However, there are classes of problems containing uncertainty that arise in areas such as contingent planning, adversarial game playing, control design, and model checking that cannot be expressed within these frameworks. Typically, such problems involve decisions or events that are beyond the control of the problem solving agent and thus cannot be handled using standard (existentially quantified) variables. Quantified CSPs and quantified Boolean formulae (QBF), which are the extensions of CSPs and SAT that allow for universally quantified variables, make it possible to model and reason with such problems, as well as other problems that contain “bounded uncertainty”. As a result, these frameworks have been attracting significant interest in recent years. The main advances have been achieved in the area of QBF where numerous solvers have been implemented and real problems of considerable size have been tackled. There is also a significant body of work on quantified numerical constraints over continuous domains, while research works on quantified constraint satisfaction problems (QCSPs) with discrete finite domains have started to emerge. With this special issue of Constraints we aim to group together and reflect the state of the art in these rapidly developing areas of research. The papers in this special issue concern the three areas of reasoning with quantified constraints highlighted above.