How to Determine the Expressive Power of Constraints

Some constraint languages are more powerful than others because they allow us to express a larger collection of problems. In this paper, we give a precise meaning to this concept of expressive power for constraints over finite sets of values. The central result of the paper is that the expressive power of a given set of constraint types is determined by certain algebraic properties of the underlying relations. These algebraic properties can be calculated by solving a particular constraint satisfaction problem, which we call an 'indicator problem'. We discuss the connection between expressive power and computational complexity, and show that indicator problems provide a simple method to test for tractability.     

General Properties and Termination Conditions for Soft Constraint Propagation

Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables' values in each soft constraint are associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained constraint problems.Classical constraint propagation has been extended and adapted to soft constraints by defining a schema for soft constraint propagation [8]. On the other hand, in [1–3] it has been proven that most of the well known constraint propagation algorithms for classical constraints can be cast within a single schema.In this paper we combine these two schemas and we provide a more general framework where the schema of [3] can be used for soft constraints. In doing so, we generalize the concept of soft constraint propagation, and we provide new sufficient and independent conditions for its termination.     

Constraints and universal algebra

In this paper we explore the links between constraint satisfaction problems and universal algebra. We show that a constraint satisfaction problem instance can be viewed as a pair of relational structures, and the solutions to the problem are then the structure preserving mappings between these two relational structures. We give a number of examples to illustrate how this framework can be used to express a wide variety of combinatorial problems, many of which are not generally considered as constraint satisfaction problems. We also show that certain key aspects of the mathematical structure of constraint satisfaction problems can be precisely described in terms of the notion of a Galois connection, which is a standard notion of universal algebra. Using this result, we obtain an algebraic characterisation of the property of minimality in a constraint satisfaction problem. We also obtain a similar algebraic criterion for determining whether or not a given set of solutions can be expressed by a constraint satisfaction problem with a given structure, or a given set of allowed constraint types. This revised version was published online in June 2006 with corrections to the Cover Date.     

A characterization of convex problems in decentralized control

We consider the problem of constructing optimal decentralized controllers. We formulate this problem as one of minimizing the closed-loop norm of a feedback system subject to constraints on the controller structure. We define the notion of quadratic invariance of a constraint set with respect to a system, and show that if the constraint set has this property, then the constrained minimum-norm problem may be solved via convex programming. We also show that quadratic invariance is necessary and sufficient for the constraint set to be preserved under feedback. These results are developed in a very general framework, and are shown to hold in both continuous and discrete time, for both stable and unstable systems, and for any norm. This notion unifies many previous results identifying specific tractable decentralized control problems, and delineates the largest known class of convex problems in decentralized control. As an example, we show that optimal stabilizing controllers may be efficiently computed in the case where distributed controllers can communicate faster than their dynamics propagate. We also show that symmetric synthesis is included in this classification, and provide a test for sparsity constraints to be quadratically invariant, and thus amenable to convex synthesis.     

A characterization of convex problems in decentralized Control/sup */

We consider the problem of constructing optimal decentralized controllers. We formulate this problem as one of minimizing the closed-loop norm of a feedback system subject to constraints on the controller structure. We define the notion of quadratic invariance of a constraint set with respect to a system, and show that if the constraint set has this property, then the constrained minimum-norm problem may be solved via convex programming. We also show that quadratic invariance is necessary and sufficient for the constraint set to be preserved under feedback. These results are developed in a very general framework, and are shown to hold in both continuous and discrete time, for both stable and unstable systems, and for any norm. This notion unifies many previous results identifying specific tractable decentralized control problems, and delineates the largest known class of convex problems in decentralized control. As an example, we show that optimal stabilizing controllers may be efficiently computed in the case where distributed controllers can communicate faster than their dynamics propagate. We also show that symmetric synthesis is included in this classification, and provide a test for sparsity constraints to be quadratically invariant, and thus amenable to convex synthesis.     

Implementing a Test for Tractability

The question of determining which sets of constraints give rise to NP-complete problems, and which give rise to tractable problems, is an important open problem in the theory of constraint satisfaction. It has been shown in previous papers that certain sufficient conditions for tractability and NP-completeness can be identified using algebraic properties of relations, and that these conditions can be tested by solving a particular form of constraint satisfaction problem (the so-called indicator problem).This paper describes a program which can solve the relevant indicator problems for arbitrary sets of constraints over small domains, and for some sets of constraints over larger domains. The main innovation in the program is its ability to deal with the many symmetries present in the problem; it also has the ability to preserve symmetries in cases where this speeds up the solution.Using this program, we have systematically investigated the complexity of all individual binary relations over a domain of size four or less, and of all individual ternary relations over a domain of size three or less. This automated analysis includes the derivation of more than 450 000 new NP-completeness results, and precisely identifies the small set of individual relations which cannot be classified as either tractable or NP-complete using the algebraic conditions presented in previous papers.     

Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Constraint retraction can be described, in general, as the possibility of deleting a previously stated piece of information. This is obviously very convenient in many programming frameworks, especially in those that involve some level of interaction between the user and the system, or also in those concerning rescheduling or replanning. Nevertheless, constraint retraction is usually not provided in current constraint programming environments. This is mainly due to its high complexity and also to its non-monotonic nature, which would make most of such systems much more complex to reason with. In this paper we avoid these problems by considering a specific constraint programming framework, called clpFD, that is, constraint logic programming (CLP) over finite domain (FD) constraints. We propose an algorithm which deletes a constraint from a set of FD constraints, while maintaining partial arc-consistency, which is usual in this programming framework. What is crucial is that the retraction operation we propose is incremental, in that it follows the chain of dependencies among variables which are set by the nature of the FD constraints, and by doing so it updates only the part of the constraint set which is affected by the deletion. We also detail how constraint retraction can be incorporated in the FD constraint solver and we evaluate its behavior within the clpFD system. Experimental results on usual benchmarks, on classes of problems of increasing connectivity, and also on a real-life problem show that in almost all cases the use of our retraction algorithm provides great speed-up with respect to standard methods while not slowing down the clpFD system when no retraction is performed. This provides the system with an efficient way of retracting constraints while not changing its performance when the user does not want to use this new feature.     

MiniBrass: Soft constraints for MiniZinc

Over-constrained problems are ubiquitous in real-world decision and optimization problems. Plenty of modeling formalisms for various problem domains involving soft constraints have been proposed, such as weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures. In terms of modeling languages, however, the field of soft constraints lags behind the state of the art in classical constraint optimization. We introduce MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially ordered valuation structures (PVS) that is implemented as an extension of MiniZinc and MiniSearch. We first demonstrate the adequacy of PVS to naturally augment partial orders with a combination operation as used in soft constraints. Moreover, we provide the most general construction of a c-semiring from an arbitrary PVS. Both arguments draw upon elements from category theory. MiniBrass turns these theoretical considerations into practice: It offers a generic extensible PVS type system, reusable implementations of specific soft constraint formalisms as PVS types, operators for complex PVS products, and morphisms to transform PVS. MiniBrass models are compiled into MiniZinc to benefit from the wide range of solvers supporting FlatZinc. We evaluated MiniBrass on 28 “softened” MiniZinc benchmark problems with six different solvers. The results demonstrate the feasibility of our approach.     

Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

From soft constraints to bipolar preferences: modelling framework and solving issues

Real-life problems present several kinds of preferences. We focus on problems with both positive and negative preferences, which we call bipolar preference problems. Although seemingly specular notions, these two kinds of preferences should be dealt with differently to obtain the desired natural behaviour. We technically address this by generalising the soft constraint formalism, which is able to model problems with one kind of preference. We show that soft constraints model only negative preferences, and we add to them a new mathematical structure which allows to handle positive preferences as well. We also address the issue of the compensation between positive and negative preferences, studying the properties of this operation. Finally, we extend the notion of arc consistency to bipolar problems, and we show how branch and bound (with or without constraint propagation) can be easily adapted to solve such problems.     

Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.     

Relatively quantified constraint satisfaction

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.     

High-Order Consistency in Valued Constraint Satisfaction

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.     

A note on some collapse results of valued constraints

Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints.     

Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Maxk-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a constraint language for which Max CSP has a hard gap at location 1; i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the constraints are satisfiable. All constraint languages, for which the CSP problem (i.e., the problem of deciding whether all constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any constraint language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P=NP. We then apply this result to Max CSP restricted to a single constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P≠NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.     

The Complexity of Reasoning with Global Constraints

Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.     

An analysis of expressiveness and design issues for the generalized temporal role-based access control model

The generalized temporal role-based access control (GTRBAC) model provides a comprehensive set of temporal constraint expressions which can facilitate the specification of fine-grained time-based access control policies. However, the issue of the expressiveness and usability of this model has not been previously investigated. In this paper, we present an analysis of the expressiveness of the constructs provided by this model and illustrate that its constraints-set is not minimal. We show that there is a subset of GTRBAC constraints that is sufficient to express all the access constraints that can be expressed using the full set. We also illustrate that a nonminimal GTRBAC constraint set can provide better flexibility and lower complexity of constraint representation. Based on our analysis, a set of design guidelines for the development of GTRBAC-based security administration is presented.     

The complexity of constraint satisfaction games and QCSP

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true.While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.     

Acquiring Both Constraint and Solution Preferences in Interactive Constraint Systems

Constraints are useful to model many real-life problems. Soft constraints are even more useful, since they allow for the use of preferences, which are very convenient in many real-life problems. In fact, most problems cannot be precisely defined by using hard constraints only.However, soft constraint solvers usually can only take as input preferences over constraints, or variables, or tuples of domain values. On the other hand, it is sometimes easier for a user to state preferences over entire solutions of the problem.In this paper, we define an interactive framework where it is possible to state preferences both over constraints and over solutions, and we propose a way to build a system with such features by pairing a soft constraint solver and a learning module, which learns preferences over constraints from preferences over solutions. We also describe a working system which fits our framework, and uses a fuzzy constraint solver and a suitable learning module to search a catalog for the best products that match the user's requirements.     

Resolving inconsistencies and redundancies in declarative process models

Declarative process models define the behaviour of business processes as a set of constraints. Declarative process discovery aims at inferring such constraints from event logs. Existing discovery techniques verify the satisfaction of candidate constraints over the log, but completely neglect their interactions. As a result, the inferred constraints can be mutually contradicting and their interplay may lead to an inconsistent process model that does not accept any trace. In such a case, the output turns out to be unusable for enactment, simulation or verification purposes. In addition, the discovered model contains, in general, redundancies that are due to complex interactions of several constraints and that cannot be cured using existing pruning approaches. We address these problems by proposing a technique that automatically resolves conflicts within the discovered models and is more powerful than existing pruning techniques to eliminate redundancies. First, we formally define the problems of constraint redundancy and conflict resolution. Second, we introduce techniques based on the notion of automata-product monoid, which guarantees the consistency of the discovered models and, at the same time, keeps the most interesting constraints in the pruned set. The level of interestingness is dictated by user-specified prioritisation criteria. We evaluate the devised techniques on a set of real-world event logs.