We propose to exploit cycles in the constraint network of a Constraint Satisfaction Problem (CSP) to vehicle constraint propagation and improve the effectiveness of local consistency algorithms. We focus our attention on the consistency property Partition-One Arc-Consistency (POAC), which is a stronger variant of Singleton Arc-Consistency (SAC). We modify the algorithm for enforcing POAC to operate on a minimum cycle basis (MCB) of the incidence graph of the CSP. We empirically show that our approach improves the performance of problem solving and constitutes a novel and effective localization of consistency algorithms. Although this paper focuses on POAC, we believe that exploiting cycles, such as MCBs, is applicable to other consistency algorithms and that our study opens a new direction in the design of consistency algorithms. This research is documented in a technical report (Woordward, Choueiry, and Bessiere 2016). http://consystlab.unl.edu/our_work/StudentReports/TR-UNL-CSE-2016-0004.pdf

In Constraint Processing, many algorithms for enforcing the same level of local consistency may exist. The performance of those algorithms varies widely. In order to understand what problem features lead to better performance of one algorithm over another, we utilize an algorithm configurator to tune the parameters of a random problem generator and maximize the performance difference of two consistency algorithms for enforcing constraint minimality. Our approach allowed us to generate instances that run 1000 times faster for one algorithm over the other.

The tractability of a Constraint Satisfaction Problem (CSP)is guaranteed by a direct relationship between its consistencylevel and a structural parameter of its constraint network suchas the treewidth. This result is not widely exploited in practicebecause enforcing higher-level consistencies can be costlyand can change the structure of the constraint network andincrease its width. Recently, R(*,m)C was proposed as a relational consistency property that does not modify the structureof the graph and, thus, does not affect its width. In this paper,we explore two main strategies, based on a tree decomposition of the CSP, for improving the performance of enforcingR(*,m)C and getting closer to the above tractability condition. Those strategies are: a) localizing the application ofthe consistency algorithm to the clusters of the tree decomposition, and b) bolstering constraint propagation betweenclusters by adding redundant constraints at their separators,for which we propose three new schemes. We characterizethe resulting consistency properties by comparing them, theoretically and empirically, to the original R(*,m)C and thepopular GAC and maxRPWC, and establish the benefits ofour approach for solving difficult problems.

Computing the minimal network of a Constraint Satisfaction Problem (CSP) is a useful and difficult task. Two algorithms, PerTuple and AllSol, were proposed to this end. The performances of these algorithms vary with the problem instance. We use Machine Learning techniques to build a classifier that predicts which of the two algorithms is likely to be more effective.

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) for binary CSPs. In this paper, we introduce RNIC, the extension of NIC to non-binary CSPs, and describe a practical algorithm for enforcing it. We propose an adaptive strategy to weaken or strengthen this property based on the connectivity of the network. We demonstrate the effectiveness of RNIC as a full lookahead strategy during search for solving difficult benchmark problems.

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a strong local consistency property for binary CSPs. While enforcing NIC can significantly filter the variables domains, the proposed algorithm is too costly to be used on dense graphs or for lookahead during search. In this paper, we introduce and characterize Relational Neighborhood Inverse Consistency (RNIC) as a local consistency property that operates on the dual graph of a non-binary CSP. We describe and characterize a practical algorithm for enforcing it. We argue that defining RNIC on the dual graph unveils unsuspected opportunities to reduce the computational cost of our algorithm and increase its filtering effectiveness. We show how to achieve those effects by modifying the topology of the dual graph, yielding new variations the RNIC property. We also introduce an adaptive strategy to automatically select the appropriate property to enforce given the connectivity of the dual graph. We integrate the resulting techniques as full lookahead strategies in a backtrack search procedure for solving CSPs, and demonstrate the effectiveness of our approach for solving known difficult benchmark problems.

Substitutability, interchangeability and related concepts in Constraint Programming were introduced approximately twenty years ago and have given rise to considerable subsequent research. We survey this work, classify, and relate the different concepts, and indicate directions for future work, in particular with respect to making connections with research into symmetry breaking. This paper is a condensed version of a larger work in progress.

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R ( *,m ) C, which is equivalent to m-wise consistency proposed in relational databases. We also define wR ( *,m ) C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tightening the existing relations and without introducing new ones. We empirically show that wR(*,m)C solves in a backtrack-free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.

The Fourth Symposium on Abstraction, Reformulation, and Approximation (SARA) took place at Horseshoe Bay Resort and Conference Club, Lake LBJ, Texas, from 26 to 29 July 2000. The talks at the conference captured a cross section of application domains and included invited talks and two panels.