Weighted constraint satisfaction problem
In artificial intelligence and operations research, a Weighted Constraint Satisfaction Problem, also known as Valued Constraint Satisfaction Problem, is a generalization of a constraint satisfaction problem where some of the constraints can be violated and in which preferences among solutions can be expressed. This generalization makes it possible to represent more real-world problems, in particular those that are over-constrained, or those where we want to find a minimal-cost solution among multiple possible solutions.
Formal definition
A Weighted Constraint Network, aka Cost Function Network, is a triplet where is a finite set of discrete variables, is a finite set of soft constraints and is either a natural integer or.Each soft constraint involves an ordered set of variables, called its scope, and is defined as a cost function from to where is the set of possible instantiations of. When an instantiation is given the cost, i.e.,, it is said forbidden. Otherwise it is permitted with the corresponding cost.
In WCSP, specific subclass of Valued CSP, costs are combined with the specific operator defined as:
The partial inverse of is defined by:
Without any loss of generality, the existence of a nullary constraint as well as the presence of a unary constraint for every variable is assumed.
The total cost of a complete instantiation is the bounded sum of the cost of on for all soft constraint, including the nullary cost and the unary costs for of the variables in.
Considering a WCN/CFN, the usual task of WCSP is to find a complete instantiation with a minimal cost.
Other tasks in the related field of graphical model can be defined.
Resolution of binary/ternary WCSPs
Approach with cost transfer operations
Node consistency and Arc consistency, introduced for the Constraint Satisfaction Problem, have been studied later in the context of WCSP.Furthermore, several consistencies about the best form of arc consistency have been proposed: Full Directional Arc consistency , Existential Directional Arc consistency , Virtual Arc consistency and Optimal Soft Arc consistency .
Algorithms enforcing such properties are based on Equivalence Preserving Transformations that allow safe moves of costs among constraints. Three basic costs transfer operations are:
- Project : cost transfer from constraints to unary constraints
- ProjectUnary : cost transfer from unary constraint to nullary constraint
- Extend : cost transfer from unary constraint to constraint
Approach without cost transfer operations
An alternative to cost transfer algorithms is the algorithm PFC-MRDAC which is a classical branch and bound algorithm that computes lower bound at each node of the search tree, that corresponds to an under-estimation of the cost of any solution that can be obtained from this node. The cost of the best solution found is. When, then the search tree from this node is pruned.Another more recent approach is based on super-reparametrizations which allows to relax the problem to compute tighter bounds.
Resolution of n-ary WCSPs
Cost transfer algorithms have been shown to be particularly efficient to solve real-world problem when soft constraints are binary or ternary.For soft constraints of large arity, cost transfer becomes a serious issue because the risk of combinatorial explosion has to be controlled.
An algorithm, called GAC-WSTR, has been proposed to enforce a weak version of the property Generalized Arc Consistency on soft constraints defined extensionally by listing tuples and their costs.
This algorithm combines two techniques, namely, Simple Tabular Reduction and cost transfer. Values that are no longer consistent with respect to GAC are identified and
minimum costs of values are computed. This is particularly useful for efficiently performing projection operations that are required to establish GAC.
Global cost functions with a dedicated semantic and polytime complexity have been also studied.
Solvers
https://www.ics.uci.edu/~dechter/software.html- '''https://miat.inrae.fr/toulbar2'''