Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
AIJ Journal 2024 Journal Article
AIJ Journal 2023 Journal Article
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1.
IJCAI Conference 2017 Conference Paper
CP solvers predominantly use arc consistency (AC) as the default propagation method. 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. We seek a balance between the efficiency of triangle consistencies and the ease of implementation of singleton ones. Using the recently proposed variant of SAC called Neighborhood SAC as basis, we propose a family of weaker singleton consistencies. We study them theoretically, comparing their pruning power to existing consistencies. We make a detailed experimental study using a very simple algorithm for their implementation. Results demonstrate that they outperform the existing propagation techniques, often by orders of magnitude, on a wide range of problems.
AAAI Conference 2015 Conference Paper
We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experiments show large differences in favor of our approaches.
AAAI Conference 2013 Conference Paper
One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerous specialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC), have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper, we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max restricted pairwise consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.
AAAI Conference 2012 Conference Paper
Table constraints are very 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 an efficient algorithm for table constraints that achieves a stronger local consistency than GAC. This algorithm, called maxRPWC+, is based on the local consistency maxRPWC and allows the efficient handling of intersecting table constraints. Experimental results from benchmark problems demonstrate that maxRPWC+ is clearly more robust than a state-of-the-art GAC algorithm in classes of problems with interleaved table constraints, being orders of magnitude faster in some of these classes.
AIJ Journal 2008 Journal Article
In non-binary constraint satisfaction problems, the study of local consistencies that only prune values from domains has so far been largely limited to generalized arc consistency or weaker local consistency properties. This is in contrast with binary constraints where numerous such domain filtering consistencies have been proposed. In this paper we present a detailed theoretical, algorithmic and empirical study of domain filtering consistencies for non-binary problems. We study three domain filtering consistencies that are inspired by corresponding variable based domain filtering consistencies for binary problems. These consistencies are stronger than generalized arc consistency, but weaker than pairwise consistency, which is a strong consistency that removes tuples from constraint relations. Among other theoretical results, and contrary to expectations, we prove that these new consistencies do not reduce to the variable based definitions of their counterparts on binary constraints. We propose a number of algorithms to achieve the three consistencies. One of these algorithms has a time complexity comparable to that for generalized arc consistency despite performing more pruning. Experiments demonstrate that our new consistencies are promising as they can be more efficient than generalized arc consistency on certain non-binary problems.
AIJ Journal 2008 Journal Article
We make a number of contributions to the study of the Quantified Constraint Satisfaction Problem (QCSP). The QCSP is an extension of the constraint satisfaction problem that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. In this paper we report significant contributions to two very different methods for solving QCSPs. The first approach is to implement special purpose algorithms for QCSPs; and the second is to encode QCSPs as Quantified Boolean Formulas and then use specialized QBF solvers. The discovery of particularly effective encodings influenced the design of more effective algorithms: by analyzing the properties of these encodings, we identify the features in QBF solvers responsible for their efficiency. This enables us to devise analogues of these features in QCSPs, and implement them in special purpose algorithms, yielding an effective special purpose solver, QCSP-Solve. Experiments show that this solver and a highly optimized QBF encoding are several orders of magnitude more efficient than the initially developed algorithms. A final, but significant, contribution is the identification of flaws in simple methods of generating random QCSP instances, and a means of generating instances which are not known to be flawed.
AIJ Journal 2000 Journal Article
We extend the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to consider constraints of the form x1−y1≤r1 ∨⋯∨xn−yn≤rn, where x1, …, xn, y1, …, yn are variables ranging over the real numbers, r1, …, rn are real constants, and n≥1. This is a wide class of temporal constraints that can be used to model a variety of problems in temporal reasoning, scheduling, planning, and temporal constraint databases. We have implemented several progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints: backtracking, backjumping, three variations of forward checking, and forward checking with backjumping. We have partially ordered the above algorithms according to the number of visited search nodes and the number of performed consistency checks. Although our problem is non-binary, our results agree with the results of Kondrak and van Beek who consider only binary constraints. We have also studied the performance of the above algorithms experimentally using randomly generated sets of data and job shop scheduling problems. The experiments with random instances allowed us to locate the hard region for this class of problems. The results show that hard problems occur at a critical value of the ratio of disjunctions to variables.
AIJ Journal 2000 Journal Article
Many constraint satisfaction problems can be naturally and efficiently modelled using non-binary constraints like the “all-different” and “global cardinality” constraints. Certain classes of these non-binary constraints are “network decomposable” as they can be represented by binary constraints on the same set of variables. We compare theoretically the levels of consistency which are achieved on non-binary constraints to those achieved on their binary decomposition. We present many results about the level of consistency achieved by the forward checking algorithm and its various generalizations to non-binary constraints. We also compare the level of consistency achieved by arc-consistency and its generalization to non-binary constraints, and identify special cases of non-binary decomposable constraints where weaker or stronger conditions, than in the general case, hold. We also analyze the cost, in consistency checks, required to achieve certain levels of consistency, and we present experimental results on benchmark domains that demonstrate the practical usefulness of our theoretical analysis.
AAAI Conference 1999 Conference Paper
We perform a detailed theoretical and empirical comparison of the dual and hidden variable encodings of non-binary constraint satisfaction problems. We identify a simple relationship between the two encodings by showing how we can translate between the two by composing or decomposing relations. This translation suggeststhat we will tend to achieve more pruning in the dual than in the hidden variable encoding. We prove that achieving arc-consistency on the dual encoding is strictly stronger than achieving arc-consistency on the hidden variable, and this itself is equivalent to achieving generalized arc-consistency on the original (non-binary) problem. We also prove that, as a consequence of the unusual topology of the constraint graph in the hidden variable encoding, inverse consistencies like neighborhood inverse consistency and path inverse consistency collapse down onto arc-consistency. Finally, we propose the “double encoding”, which combines together both the dual and the hidden variable encodings.
IJCAI Conference 1999 Conference Paper
We perform a comprehensive theoretical and experimental analysis of the use of all-different constraints. We prove that generalized arc-consistency on such constraints lies between neighborhood inverse consistency and, under a simple restriction, path inverse consistency on the binary representation of the problem. By generalizing the arguments of Kondrak and van Beek, we prove that a search algorithm that maintains generalized arc-consistency on all-different constraints dominates a search algorithm that maintains arc-consistency on the binary representation. Our experiments show the practical value of achieving these high levels of consistency. For example, we can solve almost all benchmark quasigroup completion problems up to order 25 with just a few branches of search. These results demonstrate the benefits of using non-binary constraints like all-different to identify structure in problems.
AAAI Conference 1998 Conference Paper
Weextendthe framework of simple temporalproblems studied originally by Dechter, MeiriandPearl to consider constraints of the formxl - yl 1. Wehave implemented four progressively moreefficient algorithmsfor the consistencychecking problemfor this class of temporalconstraints. We havepartially orderedthose algorithmsaccordingto the number of visited search nodesand the number of performedconsistencychecks. Finally, wehavecarried out a series of experiments onthe location of the hard region. Theresults showthat hard problemsoccur at a critical valueof the ratio of disjunctionsto variables. Thisvalue is between 6 and7.