{'fraction_non_alphanumeric': 0.05058867501401607, 'fraction_numerical': 0.012296766959446832, 'mean_word_length': 3.8580118020880616, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 43, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Algebraic Theory of Complexity for Discrete Optimisation

Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function, which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach to studying the complexity of discrete optimisation. We use this approach to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification of complexity for the Boolean case.

Here we adopt a very general framework where each problem instance is specified by a set of variables, a set of possible values for those variables, and a set of constraints. Each combination of values allowed by each constraint has an associated cost, and the goal is to find an assignment with minimal total cost. This simple abstract mathematical framework can be used to express discrete optimisation problems arising in a wide variety of fields, including operational research (scheduling, resource utilisation, transportation), computer vision (region segmentation, object recognition, image enhancement), automated reasoning (Max SAT, Min ONES), graph theory (Min-Cut, Maximum Independent Set), and many others.
In the special case when all costs are zero, the problem we are studying collapses to the standard constraint satisfaction problem (CSP). The general CSP is NP-hard, and so is unlikely to have a polynomialtime algorithm. However, there has been much success in finding tractable fragments of the CSP by restricting the types of relation allowed in the constraints. A set of allowed relations has been called a constraint language [27]. For some constraint languages the associated constraint satisfaction problems with constraints chosen from that language are solvable in polynomial-time, whilst for other constraint languages this class of problems is NP-hard [28,27,22]; these two cases are referred to as tractable languages and NP-hard languages, respectively. Dichotomy theorems, which classify each possible constraint language as either tractable or NP-hard, have been established for languages over 2-element domains [34], 3-element domains [13], for conservative languages [15,1], and maximal languages [11,12].
The more general framework we consider here, which allows non-zero costs, is also NP-hard, but again we can try to identify tractable fragments by restricting the types of allowed constraints. Each type of constraint is specified by a rational-valued function defined on a set of tuples, which specifies the cost associated with each allowed tuple of values. Such a function is called a weighted relation, and a set of weighted relations will be called a valued constraint language [16]. Much less is known about the complexity of the optimisation problems associated with different valued constraint languages, although some results have been obtained for certain special cases. In particular, a complete characterisation of complexity has been obtained for valued constraint languages over a 2-element domain [16]. This result generalises a number of earlier results for particular optimisation problems such as MAX-SAT [18] and MIN-ONES [19]. A complete classification has also been obtained for valued constraint languages containing all unary {0, 1}valued weighted relations (such languages are called conservative) [30]. This result generalises a number of earlier results such as GRAPH MIN-COST-HOM [25] and DIGRAPH MIN-COST-HOM [37].
One class of weighted relations that has been extensively studied and shown to be tractable is the class of submodular functions [19,16,29,21,30,41].
In the classical CSP framework it has been shown that the complexity of any constraint language over any finite domain is determined by certain algebraic properties known as polymorphisms [28,27]. This result has reduced the problem of the identification of tractable constraint languages to that of the identification of suitable sets of polymorphisms. In other words, it has been shown to be enough to study just those constraint languages which are characterised by having a given set of polymorphisms. Using this algebraic approach, considerable progress has now been made towards a complete characterisation of the complexity of constraint languages over finite domains of arbitrary size [22,14,4,2,3,5].
In this paper, we introduce a new algebraic construct which we call a weighted polymorphism. We are able to show that the weighted polymorphisms of a valued constraint language are sufficient to determine the complexity of that language. In addition, we are able to define a Galois connection between valued constraint languages and sets of weighted polymorphisms, and characterise the closed sets on both sides.
The Galois connection we establish here can be used in the search for tractable valued constraint languages in a very similar way to the use of polymorphisms in the search for tractable constraint languages in the classical CSP. First, we need only consider valued constraint languages characterised by weighted polymorphisms. This greatly simplifies the search for a characterisation of all tractable valued constraint languages. Second, we will show below that any tractable valued constraint language must have an associated non-trivial weighted polymorphism. Hence the results of this paper provide a powerful new set of tools for analysing the complexity of finite-domain discrete optimisation problems. In fact, a recent result on the power of linear programming for valued constraint languages builds on weighted polymorphisms [38].
The structure of the paper is as follows. In Section 2 we introduce the general framework of the Valued Constraint Satisfaction Problem (VCSP) and define the notion of expressibility. In Section 3 we focus on the classical Constraint Satisfaction Problem and show how it fits in the VCSP framework as a special case. We briefly recall the notion of polymorphism, and the Galois connection that has been so fruitful in the study of the complexity of the classical Constraint Satisfaction Problem. In Sections 4 and 5 we introduce weighted relational clones (valued constraint languages closed under expressibility and certain other operations) and the corresponding closed sets of weighted polymorphisms, which we call weighted clones. We then state our main result: weighted relational clones are in 1-to-1 correspondence with weighted clones. In Section 6 we give proofs of the theorems establishing this Galois connection. In Section 7 we use the algebraic theory to establish necessary conditions that must be satisfied by any tractable valued constraint language. Using these results, we obtain a complete classification for the Boolean case in Section 8. Finally, in Section 9, we state some conclusions and outline directions for future work.

The Valued Constraint Satisfaction Problem
For any set D, the set of tuples of length r over D is denoted by D r , and a subset of D r is called a relation over D of arity r. A (partial) function ̺ from D r to Q associates a rational 1 weight with each of the tuples in some subset of D r , and so will be called a weighted relation on D of arity r.
The idea of a weighted relation is very general, and can be used to define a wide variety of discrete optimisation problems. The general framework we shall use for such problems is defined as follows.
Definition 2.1. An instance of the valued constraint satisfaction problem, (VCSP), is a triple P = V, D, C where: V is a finite set of variables; D is a finite set of possible values; C is a finite multiset of constraints. Each element of C is a pair c = σ, ̺ where σ is a tuple of variables called the scope of c, and ̺ is a weighted relation on D of arity |σ|.
An assignment for P is a mapping s : V → D. The cost of an assignment s, denoted Cost P (s), is given by the sum of the weights assigned to the restrictions of s onto each constraint scope, that is, If ̺(s(v 1 ), s(v 2 ), . . . , s(v m )) is undefined for some v 1 , v 2 , . . . , v m , ̺ ∈ C, then the assignment s is said to be infeasible and Cost P (s) is undefined.
A solution to P is a feasible assignment with minimal cost.

Example 2.2 (MIN-CUT).
In graph theory a cut of a graph is a partition of the vertices into two disjoint sets. The size of a cut is the number of edges of the graph that intersect both sides of this partition. The MIN-CUT problem for a graph is to find a cut with the smallest possible size. This problem can be solved in polynomial-time [32]. The MIN-CUT problem for the graph (V, E) can be expressed as an instance V, {0, 1}, C of VCSP by setting C = { e, ̺ = | e ∈ E}, where ̺ = is the binary weighted relation on the set {0, 1} defined by: Any assignment for this VCSP instance partitions the elements of V into those assigned the value 0 and those assigned the value 1. The cost of the assignment is equal to the size of the corresponding cut.

Example 2.3 (MAX-CUT).
The MAX-CUT problem for a graph is to find a cut with the largest possible size. This problem is NP-hard [23]. The MAX-CUT problem for the graph (V, E) can be expressed as an instance V, {0, 1}, C of VCSP by setting C = { e, ̺ = | e ∈ E}, where ̺ = is the binary weighted relation on the set {0, 1} defined by: given. The cost of a homomorphism f from G to H is then defined to be u∈V G c u (f (u)). The DIGRAPH MIN-COST-HOM problem is to find a homomorphism from G to H of minimum cost [25,37]. Given a fixed digraph H = (V H , E H ), we denote by ̺ H the binary weighted relation on the set V H defined by: The DIGRAPH MIN-COST-HOM problem for input graph G = (V G , E G ) and fixed target graph A valued constraint language is any set Γ of weighted relations on some fixed set D. We define VCSP(Γ) to be the set of all VCSP instances in which all weighted relations in all constraints belong to Γ. A valued constraint language Γ is called tractable if, for every finite subset Γ ′ ⊆ Γ, there exists an algorithm solving any instance P ∈ VCSP(Γ ′ ) in polynomial time. Conversely, Γ is called NP-hard if there is some finite subset Γ ′ ⊆ Γ for which VCSP(Γ ′ ) is NP-hard. Example 2.2 shows that the valued constraint language {̺ = } is tractable, and Example 2.3 shows that the valued constraint language {̺ = } is NP-hard.
We now define a closure operator on weighted relations, which adds to a given set of weighted relations all other weighted relations which can be expressed using that set, in the sense defined below. We say that a weighted relation ̺ is expressible over a valued constraint language Γ if there exists a VCSP instance P ∈ VCSP(Γ) and a list L of variables of P such that π L (P) = ̺. We call the pair P, L a gadget for expressing ̺ over Γ.
We define Express(Γ) to be the expressive power of Γ; that is, the set of all weighted relations expressible over Γ.
Note that the list of variables L in a gadget may contain repeated entries, the sum over an empty set is zero, and the minimum over an empty set is undefined. Example 2.6. Let P be the VCSP instance with a single variable v and no constraints, and let L = v, v . Then, by Definition 2.5, Hence for any valued constraint language Γ, over any set D, Express(Γ) contains this binary weighted relation, which will be called the weighted equality relation.
The next result shows that expressibility preserves tractability.

Theorem 2.8. A valued constraint language Γ is tractable if and only if Express(Γ) is tractable; similarly, Γ is NP-hard if and only if Express(Γ) is NP-hard.
Proof. By the definition of a tractable valued constraint language, it is sufficient to show that for any finite subset Γ ′ of Express(Γ) there exists a polynomial-time reduction from VCSP(Γ ′ ) to VCSP(Γ ′′ ), where Γ ′′ is a finite subset of Γ.
Let Γ ′ be a finite subset of Express(Γ) and let P ′ be any instance of VCSP(Γ ′ ). By Definition 2.5, any weighted relation ̺ ′ ∈ Express(Γ) can be constructed by using some gadget P ̺ ′ , L where P ̺ ′ is an instance of VCSP(Γ). Hence we can simply replace each constraint in P ′ which has a weighted relation ̺ ′ not already in Γ with the corresponding gadget to obtain an instance P of VCSP(Γ) which is equivalent to P ′ . The maximum size of any of the gadgets used is a constant determined by the finite set Γ ′ , so this construction can be carried out in polynomial time in the size of P ′ . This result shows that, when trying to identify tractable valued constraint languages, it is sufficient to consider only languages of the form Express(Γ). In the following sections, we will show that such languages can be characterised using certain algebraic properties.

Classical Constraint Satisfaction
In this section we consider the special case when the weights are all zero. There is a one-to-one correspondence between the set of zero-valued weighted relations R D and the set of all relations over D. In this correspondence each weighted relation ̺ in R D is associated with the relation R(̺) containing precisely those tuples on which ̺ is defined. Similarly, each zero-valued weighted relation in R D is associated with the predicate which is true for precisely those tuples where the weighted relation is defined. Subsets of R D are sometimes referred to as crisp constraint languages [16] and VCSP(R D ) is equivalent to the classical constraint satisfaction problem, or CSP, where each assignment is either allowed (cost 0) or disallowed (infeasible, or cost undefined).
For zero-valued weighted relations this notion of addition corresponds to performing a relational join operation on the associated relations R(̺ 1 ) and R(̺ 2 ) [26]. It also corresponds to taking a conjunction of the associated predicates [14]. Moreover, minimising a weighted relation ̺ ∈ R D over one of its arguments corresponds to taking a relational projection of R(̺) onto its remaining co-ordinates. It also corresponds to existential quantification of the associated predicate over that argument. For each Γ ⊆ R D we define RelClone(Γ) to be the smallest relational clone containing Γ.
It is a straightforward consequence of Definitions 2.5 and 3.3 that the expressive power of a crisp constraint language is given by the smallest relational clone containing it, as the next result indicates. This alternative characterisation for the expressive power of a crisp constraint language was first observed in [27], and used to study the complexity of such languages using tools from universal algebra. We now give a brief summary of this algebraic approach.
For any set D, a function f : D k → D is called a k-ary operation on D.   We can extend k-ary operations to operate on tuples in a natural way, as follows. Let x 1 , . . . , x k be tuples of length r over a set D, where each x i = x i,1 , x i,2 , . . . , x i,r . We can obtain another element of D r by applying f to the tuples x i co-ordinatewise, as follows: For any set D, the mappings Pol and Inv form a Galois connection between O D and R D [9]. A characterisation of this Galois connection for finite sets D is given by the following two theorems, originally obtained for sets of relations [24,8]. As with any Galois connection [9], this means that there is a one-to-one correspondence between clones and relational clones. Together with Proposition 3.4, this result shows that the expressive power of any crisp constraint language Γ on a finite set D corresponds to a particular clone of operations on D. Hence, by Theorem 2.8, the search for tractable crisp constraint languages corresponds to a search for suitable clones of operations [27,14]. This key observation paved the way for applying deep results from universal algebra in the search for tractable constraint languages [11,15,12,13,4,2,3,5].

Weighted Relational Clones
In this section we return to the general case of weighted relations taking arbitrary values in Q in order to define the notion of a weighted relational clone. We now define a closure operator on weighted relations, which adds to a set of weighted relations all other weighted relations which can be obtained from the original set by non-negative scaling and addition of a constant.

Definition 4.2.
A weighted relation ̺ ′ ∈ Φ D can be obtained from a weighted relation ̺ ∈ Φ D by non-negative scaling and addition of constants if there exist α, β ∈ Q with α ≥ 0 such that ̺ ′ ≡ α̺ + β . We denote by Γ ∼ the smallest set of weighted relations containing Γ which is closed under non-negative scaling and addition of constants.
The next result shows that adding weighted relations that can be obtained by non-negative scaling and addition of constants preserves tractability.

Theorem 4.3. A valued constraint language Γ is tractable if and only if
Proof. By the definition of tractable valued constraint language, it is sufficient to show that for any finite Let Γ ′ be a finite subset of Γ ∼ and let P ′ be any instance of VCSP(Γ ′ ). By Definition 4.2, any weighted relation ̺ ′ ∈ Γ ∼ can be obtained by non-negative scaling and addition of constants from some weighted relation ̺ ∈ Γ. Hence we can replace each of the constraints σ, ̺ ′ in P ′ with a new constraint σ, ̺ , where ̺ ∈ Γ and ̺ ′ = α̺ + β for some non-negative rational value α and some arbitrary rational constant β, to obtain an instance P of VCSP(Γ).
The constant β is added to the cost of all assignments and so does not affect the choice of solution.
Since α is a non-negative rational value, it can be expressed as p/q for some non-negative integer p and positive integer q.
If p is non-zero, then the effect of the scale factor p/q can be simulated by taking p copies of the new constraint in P and q copies of all other constraints in P. The maximum values of p, q are constants determined by the finite set Γ ′ , so this construction can be carried out in polynomial time in the size of P ′ .
It only remains to deal with the cases where p is zero. Assume that P ′ contains k constraints of the form σ, ̺ ′ where ̺ ′ = 0̺ + β, and replace each of these with the corresponding constraint σ, ̺ to obtain a new instance, P. Let M be the maximum weight assigned by any weighted relation in the finite set Γ ′ , and let m be the minimum difference between any two distinct weights assigned by weighted relations in Γ ′ . The cost of any feasible assignment for P is greater by at most kM than the cost of the same assignment for P ′ . Hence if we also take ⌈ M k m + 1⌉ copies of all the remaining constraints of P ′ , then we obtain an instance of VCSP(Γ) with the same solutions as P ′ . Since M and m are constants determined by the finite set Γ ′ , this construction can again be carried out in polynomial time in the size of P ′ . For each Γ ⊆ Φ D we define wRelClone(Γ) to be the smallest weighted relational clone containing Γ.
It is a straightforward consequence of Definitions 2.5, 4.2 and 4.4 that, for any valued constraint language Γ ⊆ Φ D , the set of weighted relations that can be expressed using weighted relations obtained from Γ by non-negative scaling and addition of constants, is given by the smallest weighted relational clone containing Γ, as the next result indicates.

Proposition 4.5. For any
Hence, by Theorem 2.8 and Theorem 4.3, the search for tractable valued constraint languages corresponds to a search for suitable weighted relational clones.
In the next section we establish an alternative characterisation for weighted relational clones which facilitates this search.

Weighted Clones
To obtain a suitable alternative characterisation for weighted relational clones we now generalise the notion of a clone of operations, introduced in Definition 3.8, by introducing the notion of a weighted clone.
Recall that a clone of operations, C, is a set of operations on some fixed set D that contains all projections and is closed under superposition. The k-ary operations in a clone C will be denoted C (k) . Definition 5.1. We define a k-ary weighting of a clone C to be a function ω : We denote by W C the set of all possible weightings of C and by W For any weighting ω, we denote by dom(ω) the set of operations on which ω is defined. We denote by ar(ω) the arity of ω.
Since a weighting is simply a rational-valued function satisfying certain inequalities it can be scaled by any non-negative rational to obtain a new weighting. Similarly, any two weightings of the same clone of the same arity can be added to obtain a new weighting of that clone.
The notion of superposition from Definition 3.7 can also be extended to weightings in a natural way, by forming a superposition with each argument of the weighting, as follows.

Definition 5.2.
For any clone C, any ω ∈ W (k) C and any g 1 , g 2 , . . . , g k ∈ C (ℓ) , we define the superposition of ω and g 1 , . . . , g k , to be the function ω[g 1 , . . . , g k ] : C (ℓ) → Q defined by (1) Example 5.3. Let D be a totally ordered set D, and let C = Clone({max}) where max is the binary maximum operation on D. Note that C (2) contains just three binary operations: e 1 , e 2 and max. Let ω be the 2-ary weighting of C given by Note that e 2 and e Note that ω[g 1 , g 2 ] satisfies the conditions of Definition 5.1 and hence is a 2-ary weighting of C.
Example 5.4. Let C be a clone on some totally ordered set D and let max and min be binary maximum and minimum operations which are contained in C. Note that C (4) contains operations such as max[e (4) i , e j ] which returns the maximum of the ith and jth argument values. Operations of this form will be denoted max(x i , x j ).
Let ω be the 4-ary weighting of C given by 2 , e 3 , e 1 , e 2 , e

Then, by Definition 5.2 we have
2 , e Note that ω[g 1 , g 2 , g 3 , g 4 ] satisfies the conditions of Definition 5.1 and hence is a 3-ary weighting of C.
Example 5.5. Let C and ω be the same as in Example 5.4 but now consider .

By Definition 5.2 we have
does not satisfy the conditions of Definition 5.1 because, for example, we have that is not a valid weighting of C.
It follows immediately from Definition 3.7 that the sum of the weights in any superposition ω[g 1 , . . . , g k ] is equal to the sum of the weights in ω, which is zero, by Definition 5.1. However, as we have seen in Example 5.5, it is not always the case that an arbitrary superposition satisfies the other condition in Definition 5.1, that negative weights are only assigned to projections. Hence we make the following definition: Definition 5.6. If the result of a superposition is a valid weighting, then that superposition will be called a proper superposition. We are now ready to define weighted clones. C containing all zero-valued weightings of C is a weighted clone with support C. Note that W 0 C contains exactly one weighting of each possibly arity, which assigns the value 0 to all operations in C of that arity.
We now establish a link between weightings and weighted relations, which will allow us to link weighted clones and weighted relational clones. Definition 5.11. Let ̺ be a weighted relation of arity r on some set D and let ω be a k-ary weighting of some clone of operations C on the set D.
We say that ω is a weighted polymorphism of ̺ if, for any If ω is a weighted polymorphism of ̺ we say ̺ is improved by ω.
Note that, by Definition 3.9, if ̺ is improved by the weighting ω ∈ W (k) C , then every element of C (k) must be a polymorphism of ̺. Example 5.12. Consider the class of submodular functions [32]. These are precisely the functions ̺ satisfying ̺(min(x 1 , In other words, the set of submodular functions are the set of weighted relations with a 2-ary weighted polymorphism ω sub , defined by: 1 , e Submodular function minimisation is known to be tractable [32]. To define a mapping in the other direction, we need to consider the union of the sets W C over all clones C on some fixed set D, which will be denoted W D . If we have a set W ⊆ W D which may contain weightings of different clones over D, then we can extend each of these weightings with zeros, as necessary, so that they are weightings of the same clone C, given by This set of extended weightings obtained from W will be denoted W . For any set W ⊆ W D , we define wClone(W ) to be the smallest weighted clone containing W . Definition 5.14. For any W ⊆ W D , we denote by Imp(W ) the set of all weighted relations in Φ D which are improved by all weightings ω ∈ W . The set of r-ary weighted relations in Imp(W ) will be denoted Imp (r) (W ).
It follows immediately from the definition of a Galois connection [9] that, for any set D, the mappings wPol and Imp form a Galois connection between W D and Φ D , as illustrated in Figure 1. A characterisation of this Galois connection for finite sets D is given by the following two theorems, which are proved in Section 6. As with any Galois connection [9], this means that there is a one-to-one correspondence between weighted clones and weighted relational clones. Hence, by Proposition 4.5, Theorem 2.8, and Theorem 4.3, the search for tractable valued constraint languages over a finite set corresponds to a search for suitable weighted clones of operations.

Proofs of Theorems 5.15 and 5.16
Our proofs of Theorems 5.15 and 5.16 will both use the following result, which is a variant of the wellknown Farkas' Lemma used in linear programming [32,35].   Farkas 1894). Let S and T be finite sets of indices, where T is the disjoint union of two subsets, T ≥ and T = . For all i ∈ S, and all j ∈ T , let a i,j and b j be rational numbers. Exactly one of the following holds: • Either there exists a set of non-negative rational numbers {x i | i ∈ S} and a rational number C such that • Or else there exists a set of integers {y j | j ∈ T } such that j∈T y j = 0 and: for each j ∈ T ≥ , y j ≥ 0, Such a set is called a certificate of unsolvability.
We note that there is an effective procedure to decide which of the cases mentioned in Lemma 6.1 holds for any instance, and to calculate the values of the corresponding coefficients x i or y j [35]. We will prove Theorem 5.15 in two parts. First, we show in Proposition 6.2 that the set of all weighted relations improved by any given set of weightings is always a weighted relational clone. Then we show that for any finite set Γ the set of weighted relations improved by all weightings in wPol(Γ) is precisely the weighted relational clone wRelClone(Γ). Proof. Certainly Imp(W ) contains the weighted equality relation, ̺ = , since ̺ = satisfies inequality (2) in Definition 5.11 for all x i such that ̺ = (x i ) is defined. Similarly, Imp(W ) is closed under non-negative scaling, addition of constants, addition and rearrangement of arguments, since all of these operations preserve inequality (2). Hence, to show Imp(W ) is a weighted relational clone we only need to show Imp(W ) is closed under minimisation.
Let ω ∈ W be a k-ary weighting of a clone C. Since ̺ ∈ Imp(W ), we know that ̺ and ω satisfy inequality (2) for all Extend each x ′ i to a tuple x ′′ i of arity r in such a way that ̺(x ′′ i ) is minimised. Since all negative values of ω are associated with projections, we have We now prove Theorem 5.15, which states that that for any finite set D, and any finite Γ ⊂ Φ D , Imp(wPol(Γ)) = wRelClone(Γ).
We will prove the reverse inclusion, Imp(wPol(Γ)) ⊆ wRelClone(Γ), as follows. Given a weighted relation ̺ of arity r, we will show that either there exists a weighted operation ω ∈ wPol(Γ) such that ̺ ∈ Imp({ω}) or else ̺ plus some constant can be obtained by minimisation from a non-negative weighted sum of weighted relations in Γ, and hence ̺ ∈ wRelClone(Γ).
We now give the details of this argument. Let k be the number of r-tuples for which ̺ is defined and fix an arbitrary order, x 1 , . . . , x k , for these tuples. This list of tuples can be viewed as (the rows of) a matrix with k rows and r columns, which we will call S ̺ . By Proposition 4.5, ̺ ∈ wRelClone(Γ) if and only if it can be expressed using weighted relations from Γ ∼ . By Definition 2.5, a weighted relation ̺ ′ is expressible over Γ ∼ if and only if there exists an instance P ∈ VCSP(Γ ∼ ) and a list L of variables of P such that π L (P) = ̺ ′ .
We consider instances P with |D k | variables, where each variable is associated with a distinct tuple from D k . Each constraint of P is a pair S, γ for some γ ∈ Γ ∼ and some list of variables S. Each such S can be viewed as a list of k-tuples over D, and hence as a matrix over D, whose columns are these k-tuples. Since we are using P to express the defined values of ̺, it is sufficient to consider only matrices S with rows t 1 , . . . , t k such that γ(t i ) is defined for i = 1, . . . , k. For any γ ∈ Γ, a pair S, γ with this property will be called a k-match to Γ.
Each assignment to the variables of P can be seen as a mapping from k-tuples over D to D, and hence associated with an operation f ∈ O (k) D . For any list of variables S of P, we will write f (S) to denote the assignment to those variables obtained by applying f to the columns of S, viewed as a matrix. With this notation, we have that π L (P) = ̺ ′ with L = S ̺ if we can find non-negative rationals x S,γ for all k-matches to Γ, and a constant c ∈ Q, such that the following system of inequalities and equations is satisfied: Moreover, if f ∈ Pol (k) (Γ) then the left-hand-side of the corresponding inequality will be undefined, by Definition 3.9, so it is sufficient to consider only f ∈ Pol (k) (Γ). This gives us a system of inequalities and equations with rational coefficients.
If this system has a solution then ̺ ∈ wRelClone(Γ). On the other hand, if this system of equations and inequalities has no solution, then we appeal to Lemma 6.1, to get a certificate of unsolvability. That is, in this case we know that there exists a set of integers {y f | f ∈ Pol (k) (Γ)}, such that f ∈Pol (k) (Γ) y f = 0, y f < 0 only if f is a projection, and: for each k-matching S, γ of Γ, Now, consider the k-ary weighting ω of the clone Pol(Γ) defined by ω(f ) = y f for each f ∈ Pol (k) (Γ).
From (3), we can see that ω is a weighted polymorphism of every γ ∈ Γ. On the other hand, (4) shows that ω is not a weighted polymorphism of ̺.

Remark 6.3. The proof of Theorem 5.15 demonstrates the decidability of the following question: for any
finite Γ ⊆ Φ D and any weighted relation ̺ defined on D, does ̺ belong to wRelClone(Γ)?
We will prove Theorem 5.16 in two parts. First, we show in Proposition 6.4 that the set of weighted polymorphisms of any given set of weighted relations is always a weighted clone. Then we show that for any finite set W the set of weightings that improve all weighted relations in Imp(W ) is precisely the weighted clone wClone(W ). Let ω ∈ wPol (k) (Γ) and suppose ω ′ = ω[g 1 , . . . , g k ] is a proper superposition of ω, where g 1 , g 2 , . . . , g k ∈ Pol (ℓ) (Γ). We will now show that ω ′ ∈ wPol (ℓ) (Γ). Suppose ̺ is a weighted relation of arity r satisfying ω ∈ wPol({̺}), i.e., ̺ and ω satisfy inequality (2) for all , for any f ∈ Pol (k) (Γ). Hence, by Definition 5.2, we have We will make use of the following technical lemma, which shows that any weighted sum of arbitrary superpositions of a pair of weightings ω 1 and ω 2 can be obtained by taking a weighted sum of superpositions of ω 1 and ω 2 with projection operations, and then taking a superposition of the result. This result implies that any weighting which can be expressed as a weighted sum of arbitrary superpositions can also be expressed as a superposition of a weighted sum of proper superpositions. Lemma 6.5. Let C be a clone, and let ω 1 and ω 2 be weightings of C, of arity k and ℓ respectively. For any g 1 , . . . , g k ∈ C (m) and any g ′ 1 , . . . , g ′ ℓ ∈ C (m) , where ω = c 1 ω 1 [e Proof. For any f ∈ C (m) , the result of applying the right-hand side expression in equation (5) to f is: Replacing each f ′ by the equivalent superposition of h ′ with projections, we obtain: which is the result of applying the left-hand-side of Equation 5 to f .
We now prove Theorem 5.16, which states that for any finite set D, and any finite W ⊂ W D , wPol(Imp(W )) = wClone(W ).
We will prove the reverse inclusion, wPol(Imp(W )) ⊆ wClone(W ), as follows. Given any weighting ω 0 ∈ W D , we will show that either there exists a weighted relation ̺ ∈ Imp(W ) such that ω 0 ∈ wPol({̺}) or else ω 0 is equal to a non-negative weighted sum of superpositions of weightings in W , and hence ω 0 ∈ wClone(W ).
We now give the details of this argument. Let k be the arity of ω 0 , and let M = |D| k . We first observe that it is sufficient to consider weighted relations of arity M in Imp(W ). To see this, suppose there exists a weighted relation ̺ ∈ Imp(W ) with arity N > M such that ω 0 ∈ wPol({̺}) and let x 1 , . . . , x k ∈ D N be any set of tuples for which inequality (2) fails to hold for ω 0 and ̺. Let X be the k × N matrix whose rows are the tuples x 1 , . . . , x k . Since N > M it follows that some of the columns in this matrix must be equal. Moreover, if the i-th and j-th column of X are equal, then so will be the i-th and j-th entry of the tuple f (x 1 , . . . , x k ) obtained by applying any f ∈ O (k) D to these k tuples. Now let ̺ ′ be the weighted relation of arity ≤ M that depends only on the first of each of these repeated columns, and takes the same values as ̺ takes on arguments with the appropriate entries repeated. Let X ′ be the reduced form of X (with repeated columns deleted). By this approach, we can construct ̺ ′ so that ̺ ′ ∈ Imp(W ), but X ′ gives a certificate to show that ω 0 ∈ wPol({̺}), i.e., the rows of X ′ form a list of tuples for which (2) fails to hold for ω 0 and ̺ ′ .
Moreover, if we have a weighted relation ̺ ∈ Imp(W ) with arity N < M such that ω 0 ∈ wPol({̺}), then ̺ can be extended to a weighted relation ̺ ′ of arity M that does not depend on the M − N added inputs, and, hence, is also contained in Imp(W ) and is such that ω 0 ∈ wPol({̺ ′ }).
By the argument given above, there exists a weighted relation ̺ ∈ Imp(W ) such that ω 0 ∈ wPol({̺}) if and only if there exists a weighted relation ̺ M of arity M in Imp(W ) such that ω 0 ∈ wPol({̺ M }). Furthermore, by reordering the arguments of ̺ M if necessary, we can assume that ̺ M and ω 0 violate (2) on the particular list of tuples x 1 , . . . , x k given by taking the rows of a matrix, X M , whose columns are precisely the tuples in D k , ordered lexicographically. By Definition 5.11, such a weighted relation ̺ M exists if and only if the following system of inequalities can be satisfied, for all ω ∈ W and all t 1 , . . . , t ar(ω) ∈ D M such that ̺ M (t i ) is defined for i = 1, . . . , ar(ω), g∈dom(ω) ω(g) ̺ M (g(t 1 , . . . , t ar(ω) )) ≤ 0 , and, for the tuples x 1 , . . . , x k forming the rows of X M , ̺ M (x i ) is defined for i = 1, . . . , k and There is a one-to-one correspondence between operations g : D k → D and tuples t g ∈ D M , where the tuple t g contains the list of values returned by the operation g applied to the columns of X M .
Set C = Clone( ω∈W dom(ω)). We observe that, to satisfy inequality (6), for any ω ∈ W , if ̺ M (t i ) is defined for i = 1, . . . , ar(ω), then ̺ M (g(t 1 , . . . , t ar(ω) )) must be defined for all g ∈ dom(ω). To achieve this, it is sufficient to ensure that, for all g ∈ C (k) , ̺ M (t g ) is defined. All other values of ̺ M can be left undefined, as this just reduces the number of inequalities in the system.
Using superposition (Definition 5.2), we can rewrite inequalities (6) to obtain the following equivalent system: for all ω ∈ W , and all g 1 , . . . , g ar(ω) ∈ C (k) , Now, by applying Lemma 6.1 to the resulting system of inequalities, we conclude that either a solution ̺ M exists, in which case ω 0 ∈ wPol(Imp(W )), or else there exists a set of non-negative rational numbers {c ω[g 1 ,...,g ar(ω) ] | ω ∈ W , g 1 , . . . , g ar(ω) ∈ C (k) } such that for every f ∈ C (k) , ω∈W g 1 ,...,g ar(ω) By Definition 5.1, adding the left-hand side of these inequalities over all f gives 0, and so does adding the right hand sides, so each inequality must actually be an equality. In other words, ω 0 is equal to a nonnegative weighted sum of superpositions of weightings in W . Hence, by Lemma 6.5 and Remark 5.7, ω 0 is equal to a proper superposition of some element ω ′ 0 ∈ wClone(W ), so ω 0 ∈ wClone(W ).
Remark 6.6. The proof of Theorem 5.16 demonstrates the decidability of the following question: for any finite W ⊆ W D and any weighting ω defined on D, does ω belong to wClone(W )?

Necessary Conditions For Tractability
In this section, we will start to investigate the structure of weighted clones, and hence establish some necessary conditions for any valued constraint language to be tractable. Note that, by Definition 3.8, the smallest possible clone of operations over a fixed set D is the set of all projection operations on D, which is denoted J D . Proof. Let W be a weighted clone with support J D . If the weights assigned by every weighting ω ∈ W are all zero, then W is the zero-valued weighted clone W 0 J D described in Example 5.10. Otherwise, there is some ω ∈ W (of arity k) such that ω assigns positive weight to some k-ary projections and negative weights to some of the others (the sum of the weights is zero, by Definition 5.1). If we form the superposition of ω with the sequence of projections g 1 , g 2 , . . . , g k , where g i = e By adding appropriate multiples of such functions for each successive pair of indices a and b, we can obtain any desired weighting of J D . Hence, in this case W contains all possible weightings of J D , so W = W J D .
Any weighting ω which is defined only for projection operations will be called a trivial weighting, Proposition 7.2. For any set of trivial weightings W , Imp(W ) is NP-hard.
If W contains only trivial weightings, then wClone(W ) has support J D , so it is equal to W J D or W 0 J D by Proposition 7.1. Every weighting in W 0 J D is a weighted polymorphism of any possible weighted relation, by Definition 5.11. Hence Imp(W 0 J D ) = Φ D . The weighted relations that are improved by all weightings are precisely those which take at most one value. Hence Imp(W J D ) = (R D ) ∼ .
In both cases the resulting valued constraint language is NP-hard.
Now consider weightings whose values are all 0.

Proposition 7.3. For any set of zero-valued weightings W , Imp(W ) is NP-hard.
Proof. By Definition 5.11, a zero-valued weighting will be a weighted polymorphism of any weighted relation which is a total function (i.e., any weighted relation where all assignments are feasible). Some valued constraint languages containing only total functions are NP-hard [16]. For example, consider the valued constraint language consisting of the following total function: We observed in Example 2.3 that on the domain {0, 1} the problem VCSP({̺ = }) corresponds to the MAX-CUT problem which is known to be NP-hard. Over domains of size k > 2 this problem corresponds to the problem MAX-k-CUT, which is also known to be NP-hard.
Using the Galois connection developed in the previous sections, these two results tell us that any valued constraint language that is not NP-hard must have a weighted polymorphism which is non-trivial and assigns at least some non-zero weights. A weighting which assigns positive weight to at least one operation that is not a projection will be called a positive weighting. Corollary 7.4. For any finite set D, and any Γ ⊂ Φ D , either Γ is NP-hard, or else wPol(Γ) is a weighted clone containing some positive weightings.
Proof. By Proposition 6.4, in all cases wPol(Γ) is a weighted clone.
Conversely, if Γ ′ is not NP-hard, then the same argument shows that Imp(wPol(Γ ′ )) is not NP-hard, so by Propositions 7.2 and 7.3, wPol(Γ ′ ) must contain some weightings that are non-trivial and some weightings that are not zero-valued.
Choose a weighting ω ∈ wPol(Γ) that is not zero-valued, and a weighting ω ′ that is non-trivial (but may be zero-valued). If ω assigns positive weight to any non-projection, then it is a positive weighting and we are done.
Otherwise, we have that ω assigns positive weight to some projections and negative weight to some other projections. Let f be an operation on which ω ′ is defined that is not a projection, and let k be the arity of f . If we form the superposition of ω with the sequence of functions g 1 , g 2 , . . . , g ar(ω) , where g i = f if ω(e (ar(ω)) i ) is positive, and g i = e (k) 1 otherwise, then we obtain a new weighting ω[g 1 , g 2 , . . . , g ar(ω) ] which assigns positive weight to f (see Example 5.3).
Assuming that P = N P , this result tells us that tractable valued constraint languages are associated with certain kinds of weighted clones.
To obtain further information about the weighted clones associated with tractable valued constraint languages, we now consider some special kinds of operations. For any k ≥ 2, a k-ary operation f is called sharp if f is not a projection, but the operation obtained by equating any two inputs in f is a projection [20].
In other words, f is sharp if for all i, j ∈ {1, . . . , k−1} with i = j, there exists an index m ∈ {1, . . . , k−1} such that f satisfies the identity: Each of these weightings has arity k − 1, so, by the choice of ω, must not assign positive weight to any operation except (possibly) projections. Hence all non-projection operations assigned positive weight by ω are sharp.
We can obtain further details about these weighted clones by considering the possible types of sharp operations.
First, we observe that all sharp operations must satisfy the identity f (x, x, . . . , x) = x; such operations are called idempotent.
Ternary sharp operations may be classified according to their values on tuples of the form (x, x, y), (x, y, x) and (y, x, x), which must be equal to either x or y. There are precisely 8 possibilities, as listed in Table 1.
x y x y x y x y Table 1: Sharp ternary operations The first column in Table 1 corresponds to operations that satisfy the identities f (x, x, y) = f (x, y, x) = f (y, x, x) = x for all x, y ∈ D; such operations are called majority operations. The last column in the table corresponds to operations that satisfy the identities f (x, x, y) = f (x, y, x) = f (y, x, x) = y for all x, y ∈ D; such operations are called minority operations. Columns 4, 6 and 7 in Table 1 correspond to operations that satisfy the identities f (y, y, x) = f (x, y, x) = f (y, x, x) = y for all x, y ∈ D (up to permutations of inputs); such operations are called Pixley operations [33].
For any k ≥ 3, a k-ary operation f is called a semiprojection if it is not a projection, but there is an index i ∈ {1, . . . , k} such that f (x 1 , . . . , x k ) = e (k) i for all x 1 , . . . , x k ∈ D such that x 1 , . . . , x k are not pairwise distinct. In other words, a semiprojection is a particular form of sharp operation where the operation obtained by equating any two inputs is always the same projection. Columns 2,3 and 5 in Table 1 correspond to semiprojections.
The following lemma shows that the only sharp operations of arity k ≥ 4 are semiprojections.
Lemma 7.6 (Świerczkowski's Lemma [36]). Given an operation of arity ≥ 4, if every operation arising from the identification of two variables is a projection, then these projections coincide.
Hence we may refine Theorem 7.5 to obtain the following corollary.

Classification of Boolean Valued Constraint Languages
In this section, we consider the special case of valued constraint languages over a 2-valued domain, such as the Boolean domain D = {0, 1}.
There are only four unary operations on the Boolean domain, and one of these is the projection operation e (1) 1 , which is the identity operation. The remaining three unary operations are the operations given by f (x) = 0, f (x) = 1, and f (x) = 1 − x. These will be referred to as constant 0, constant 1, and inversion.
There are only two binary idempotent operations on the Boolean domain that are not projections: the operations min and max. The only sharp ternary operations are the unique majority operation (which we will call Mjrty), the unique minority operation (which we will call Mnrty), and three Pixley operations. There are no semiprojections.
Hence we can refine Corollary 7.7 even further in the special case of the Boolean domain, to limit the possibilities for weighted clones associated with tractable valued constraint languages to just nine cases. Proof. Let C be the support of W , and let ω be a positive weighting in W with minimal possible arity. Since there are no semiprojections on the Boolean domain, Corollary 7.7 tells us that ω is either unary, binary or ternary.
Consider first the case when ω is unary. Since there are just three unary operations on the Boolean domain that are not projections, scale ω so it assigns weight -1 to the projection e (1) 1 , weight a to the constant 0 operation f 0 , weight b to the constant 1 operation f 1 , and weight c to the inversion operation f ¬ . If c = 1, then ω assigns positive weight only to f ¬ and we are done. Otherwise, if f ¬ ∈ C, and hence c is defined, we consider the weighting It is straightforward to check that ω ′ assigns weight c − 1 to e (1) 1 , weight a to f 0 , weight b to f 1 and weight 0 to f ¬ . By Lemma 6.5, ω ′ belongs to W . If a = 1, then ω ′ assigns positive weight only to f 0 and we are done. Otherwise, if f 0 ∈ C, and hence a is defined, we consider the weighting It is straightforward to check that ω ′′ assigns positive weight only to f 1 . By Lemma 6.5, ω ′′ belongs to W .
Next consider the case when ω is binary. By Corollary 7.7 and our observations above about the possible binary idempotent operations on the Boolean domain, we know that ω assigns positive weight only to one or both of the operations min and max. If either of these weights is undefined (because the corresponding function does not belong to C), or zero, then we are done, so assume that ω assigns positive weight to both min and max. By taking the weighting ω + ω[e (2) 2 , e 1 ], with a suitable scaling, we can obtain a weighting ω a ∈ W that assigns weight -1 to both binary projections, weight a to min and weight 2 − a to max, for some 0 < a < 2.
If a < 1, then the weighting ω a + a 1−a ω a [min, max] assigns positive weight only to max. If a > 1, then the weighting ω a + 2−a a−1 ω a [min, max] assigns positive weight only to min. If a = 1, then ω assigns equal weight to min and max.
Finally, we consider the case when ω is ternary. By Corollary 7.7 and our observations above about the possible ternary sharp operations on the Boolean domain, we know that ω assigns positive weight to some subset of Mjrty, Mnrty and the three Boolean Pixley operations f 1 , f 2 and f 3 (corresponding to the fourth, sixth and seventh columns of Table 1). We note that f 1 [e 3 , e 3 , e 3 , e 1 ] = f 2 . Hence, if ω assigns positive weight to any Pixley operation, then we have that W also contains the weighting ω ′ = ω + ω[e (3) 2 , e 3 , e 1 , e 2 ] which assigns equal negative weight to each projection, and equal positive weight to each Pixley operation. By a suitable scaling we shall assume that ω ′ assigns weight -1 to each projection.
Suppose first that ω ′ assigns positive weight to at least one of Mjrty and Mnrty, and assigns weight 0 < w < 1 to the three Pixley operations. We note that f i [f 1 , f 2 , f 3 ] = e is non-zero, assigns weight 0 to each Pixley operation and equal negative weight to all projections. By Lemma 6.5, ω ′′ ∈ W .
Assume that ω ′′ assigns positive weight to both Mnrty and Mjrty. By taking a suitable scaling, we can obtain a weighting ω a ∈ W that assigns weight -1 to all three projections, weight a to Mnrty and weight 3 − a to Mjrty, for some 0 < a < 3.
The only remaining case is when ω ′ assigns positive weight 1 just to the three Pixley operations. In this case we note that f 1 [e 2 , f 1 ] = e 2 . Thus the function µ 1 = ω[e 1 , e 2 , f 1 ] assigns weight −1 to f 1 , +1 to Mjrty, and 0 otherwise. For i = 2, 3, we can obtain in a similar way a function µ i , which assigns weight −1 to f i and +1 to Mjrty. Then the weighting ω + µ 1 + µ 2 + µ 3 will assign positive weight only to Mjrty. Again, by Lemma 6.5, ω ′′ ∈ W .
Each of the nine types of weightings mentioned in Theorem 8.1 can be supported by a different clone, so these nine types of weightings can each generate different weighted clones.
Using the Galois connection developed above, this result tells us that any tractable valued constraint language over the Boolean domain must have as a weighted polymorphism one of nine specific kinds of weightings. Eight of these can be been shown to be sufficient to ensure tractability using the results of [16]. The only remaining case is the unary weighting that assigns positive weight to the inversion operation only. Our next result shows that having a weighted polymorphism of this kind is not a sufficient condition for tractability on its own, but if a language has any additional positive weightings as weighted polymorphisms which are not implied by this one, then it will be tractable. Proof. By Theorem 8.1, W must contain either a weighting ω ¬ that assigns positive weight to the inversion operation only, or at least one of the eight other kinds of weighting listed in Theorem 8.1 (or both). If W = wClone({ω ¬ } ∪ W 0 C ), for some unary weighting ω ¬ that assigns positive weight to the inversion operation only and C is the support of W , then we are in case (1). In this case, the weighted relation ̺ = defined in Example 2.3 is an element of Imp(W ), so Imp(W ) is NP-hard (see the proof of Proposition 7.3).
If W contains a suitable weighting ω ¬ , but W = wClone({ω ¬ } ∪ W 0 C ), then W must also contain a non-zero weighting ω of minimal possible arity such that ω ∈ wClone({ω ¬ } ∪ W 0 C ). If ω is unary, then we can use the same argument as in the proof of Theorem 8.1 to show that W must contain a unary operation that assigns positive weight to the constant 1 operation only or the constant 0 operation only.
If ω(f ) = a > 0 for some f such that f (x, . . . , x) = 1 − x, then we consider the weighting ω ′ = ω + aω ¬ [f ], and note that ω ′ (f ) = 0. By repeating this process we obtain a weighting ω ′′ which assigns positive weight only to operations f such that f (x, . . . , x) = x. Since ω has minimal arity, these must be sharp operations, so we can proceed as in the proof of Theorem 8.1 to show that case (2) holds.
Each of the eight types of weightings in case (2) is sufficient to ensure the tractability of Imp(W ), by the results of [16].
The corresponding classification for valued constraint languages over the Boolean domain was obtained in [16] using a more intricate argument involving the explicit construction of gadgets to express particular weighted relations. Here we have considered only the properties of weighted clones. Hence the valued constraint language Γ = {̺ = } is tractable, and remains tractable if we add to Γ any other weighted relations that have this weighting as a weighted polymorphism. For example, we may add unary weighted relations with a single allowed value, which allow us to fix individual variables to a desired value, and still retain tractability. It follows that ̺ = ∈ Express({̺ = }).

Conclusions
We have presented an algebraic theory of valued constraint languages that generalizes and extends the algebraic theory developed over the past few years to study the complexity of the classical constraint satisfaction problem. We have shown that the complexity of any valued constraint language over a finite domain with rational-valued costs is determined by certain algebraic properties which we have called weighted polymorphisms.
When the weights are all zero, the optimisation problem we are considering collapses to the classical constraint satisfaction problem, CSP. In previous work [28,27] it has been shown that every tractable constraint language for the CSP can be characterised by an associated clone of operations. That work initiated the use of algebraic properties in the search for tractable constraint languages, an area that has seen considerable activity in recent years; see, for instance, [11,15,14,13,29,21,4,2,3,5]. The results in this paper show that a similar result holds for the valued constraint satisfaction problem: every tractable valued constraint language is characterised by an associated weighted clone. We therefore hope that our results here will provide a similar impetus for the investigation of a much broader class of discrete optimisation problems. For example, a recent result on the power of linear programming for valued constraint languages [38] provides a characterisation of languages solvable by a standard LP relaxation in terms of weighted polymorphisms.
Many questions about the complexity of discrete optimisation problems over finite domains can now be translated into questions about the structure of weighted clones. This provides a new approach to tackling such questions by investigating the algebraic properties of weighted clones.