Weighted constraint satisfaction problem
In artificial intelligence and operations research, a Weighted Constraint Satisfaction Problem (WCSP) is a generalization of a constraint satisfaction problem (CSP) where some of the constraints can be violated (according to a violation degree) 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 (no solution can be found without violating at least one constraint), or those where we want to find a minimal-cost solution (according to a cost function) among multiple possible solutions. Formal definition. A Weighted  Constraint Network (WCN), aka Cost Function Network (CFN), is a triplet formula_1 where formula_2 is a finite set of discrete variables, formula_3 is a finite set of soft constraints and formula_4 is either a natural integer or formula_5. Each soft constraint formula_6 involves an ordered set formula_7 of variables, called its scope, and is defined as a cost function from formula_8 to formula_9 where formula_8 is the set of possible instantiations of formula_11. When an instantiation formula_12 is given the cost formula_13, i.e., formula_14, it is said forbidden. Otherwise it is permitted with the corresponding cost (0 being completely satisfactory ). In WCSP, specific subclass of Valued CSP (VCSP), costs are combined with the specific operator formula_15 defined as: formula_16. The partial inverse of formula_15 is formula_18 defined by: if formula_19, formula_20 and if formula_21, formula_22. Without any loss of generality, the existence of a nullary constraint formula_23 (a cost) as well as the presence of a unary constraint formula_24 for every variable formula_25 is assumed. The total cost of a complete instantiation formula_26 is the bounded sum of the cost of formula_27 on formula_28 for all soft constraint formula_6, including the nullary cost formula_30 and the unary costs for formula_27  of the variables in formula_2. Considering a WCN/CFN, the usual (NP-hard) 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 (NC) and Arc consistency (AC), introduced for the Constraint Satisfaction Problem (CSP), 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 (FDAC), Existential Directional Arc consistency (EDAC), Virtual Arc consistency (VAC) and Optimal  Soft Arc consistency (OSAC). Algorithms enforcing such properties are based on Equivalence Preserving Transformations (EPTs) that allow safe moves of costs among constraints. Three basic costs transfer operations are: The goal of Equivalence Preserving Transformations is to concentrate costs on the nullary constraint formula_33 and remove efficiently instantiations and values with a cost, added to formula_33, that is greater than or equal to the forbidden cost or the cost of the best solution found so far. A branch-and-bound method is typically used to solve WCSPs, with lower bound formula_33 and upper bound formula_13. 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 formula_37 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 formula_38. When formula_39, 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 (maximal arity of constraints in the problem is equal to 2 or 3). 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 formula_40, has been proposed to enforce a weak version of the property Generalized Arc Consistency (GAC) on soft constraints defined extensionally by listing tuples and their costs. This algorithm combines two techniques, namely, Simple Tabular Reduction (STR) 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 (e.g. SoftAllDifferent, SoftAmong) and polytime complexity have been also studied. Benchmarks. Many real-world WCSP benchmarks are available on http://genoweb.toulouse.inra.fr/~degivry/evalgm and https://forgemia.inra.fr/thomas.schiex/cost-function-library (older version at http://costfunction.org/en/benchmark). More MaxCSP benchmarks available on http://www.cril.univ-artois.fr/~lecoutre/#/benchmarks (deprecated site, see also http://xcsp.org/series).