Constraints Archive - Cork Constraint Computation Centre

AITopics Original Links

The Archive contains many pointers to constraints material. We are in the process of refurbishing it, but recognize that it is incomplete and somewhat out of date. Please contact us if you have any suggestions, contributions or corrections. Brief History: Many thanks to those individuals and organizations that have helped make the Constraints Archive a valuable resource. The Constraints Archive, originally known as the City University Constraints Archive, was created by Michael Jampel; the archive was maintained by David Joslin and Peg Eaton during 1996-1998, when it was split into two entities.


Set Intersection and Consistency in Constraint Networks

AAAI Conferences

In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency.


Preferences in Constraint Satisfaction and Optimization

AI Magazine

We review constraint-based approaches to handle preferences. We start by defining the main notions of constraint programming, then give various concepts of soft constraints and show how they can  be used to model quantitative preferences. We then consider how soft constraints can be adapted to handle other forms of preferences, such as bipolar, qualitative, and temporal preferences. Finally, we describe how AI techniques such as abstraction, explanation generation, machine learning, and preference elicitation, can be useful in modelling and solving soft constraints.


Set Intersection and Consistency in Constraint Networks

arXiv.org Artificial Intelligence

In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency. This generalizes row convex constraints. Various consistency results are also obtained on constraint networks where only some, in contrast to all in the existing work,constraints are tight.


Optimum Anytime Bounding for Constraint Optimization Problems Simon de Givry and G rard Verfaillie

AAAI Conferences

Edouard Belin, BP 4025, 31055 Toulouse Cedex 4, France {degivry,verfaillie}@cert.fr Abstract In this paper, we consider Constraint Optimization Problems in a Resource-Bounded context. We observe that both exact and approximate methods produce only an anytime upper bound of the optimum (in case of minimization). No lower bound, and thus no quality is available at run time. For a meta-reasoning system, it is difficult to reason on the basis of a so poor piece of information. Therefore, we discuss some ways of producing an anytime lower bound.