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.

Keywords: complexity, Galois connection, constraint optimisation, valued constraint satisfaction problems, weighted clones, weighted polymorphisms

The topic of this book is the following optimisation problem: given a set of discrete variables and a set of functions, each depending on a subset of the variables, minimise the sum of the functions over all variables. This fundamental research problem has been studied within several different contexts of discrete mathematics, computer science and artificial intelligence under different names: Min-Sum problems, MAP inference in Markov random fields (MRFs) and conditional random fields (CRFs), Gibbs energy minimisation, valued constraint satisfaction problems (VCSPs), and, for two-state variables, pseudo-Boolean optimisation.

In this book the author presents general techniques for analysing the structure of such functions and the computational complexity of the minimisation problem, and he gives a comprehensive list of tractable cases. Moreover, he demonstrates that the so-called algebraic approach to VCSPs can be used not only for the search for tractable VCSPs, but also for other questions such as finding the boundaries to the applicability of certain algorithmic techniques.

The book is suitable for researchers interested in methods and results from the area of constraint programming and discrete optimisation.

Keywords: algorithms, constraint programming (CP), constraint satisfaction problem (CSP), discrete optimization, linear programming (LP), tractability, tractable languages, valued constraint satisfaction problems (VCSPs)

In this chapter, we will survey recent results on the broad family of optimisation problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, and give examples of tractable cases.

We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well-understood, see Raghavendra [STOC'08]. However, there is no characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimisation perspective.

We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0,∞}-valued cost functions (i.e. relations), such languages have been called conservative and studied by Bulatov [LICS'03] and recently by Barto [LICS'11]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [AIJ'06] for languages over Boolean domains, by Deineko et al. [JACM'08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [STACS'10] for {0,∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom).

We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains is significantly harder than the Boolean case. The polynomial-time algorithm we present for the tractable cases is a generalisation of the submodular minimisation problem and a result of Cohen et al. [TCS'08].

Our results generalise previous results by Takhanov [STACS'10] and (a subset of results) by Cohen et al. [AIJ'06] and Deineko et al. [JACM'08]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [JACM'08], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.

Keywords: complexity, dichotomy, discrete optimisation, multimorphisms, submodularity, valued constraint satisfaction problems

The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or solving binary Valued Constraint Satisfaction Problems (VCSPs).

We study the computational complexity of classes of discrete optimisation problems given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, the only non- trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property. Our results, apart from giving complete classifications in the studied cases, provide guidance in the search for hybrid tractable classes; that is, classes of problems that are not captured by restrictions on the functions (such as submodularity) or the structure of the problem graph (such as bounded treewidth).

Furthermore, we introduce a class of problems with convex cardinality functions on cross-free sets of assignments. We prove that while imposing only one of the two conditions renders the problem NP-hard, the conjunction of the two gives rise to a novel tractable class satisfying the cross-free convexity property, which generalises the joint-winner property to problems of unbounded arity.

Keywords: discrete optimisation, convex cardinality functions, cross-free sets, Gibbs energy minimisation, MAP inference in Markov Random Fields (MRFs), Min-Sum problems, Valued Constraint Satisfaction Problems (VCSPs)

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.

Keywords: constraint optimisation, computational complexity, tractability, soft constraints, valued constraint satisfaction problems, graphical models, forbidden substructures

Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n⁶) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. Furthermore, we describe how our results translate to certain optimisation problems arising in computer vision.

Keywords: valued constraint satisfaction problems, submodular constraints, minimisation of submodular functions, min-cut, pseudo-Boolean optimisation

We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered in several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

Keywords: decomposition of submodular functions, min-cut, pseudo-Boolean optimisation, submodular function minimisation

Denote by C the class of oracles relative to which P=NP (collapsing oracles), and by S the class of oracles relative to which P≠NP (separating oracles). We present structural results on C and S. Using a diagonalization argument, we show that neither C nor S is closed under disjoint union, also known as join. We show that this implies that neither C nor S is closed under union, intersection, or symmetric difference. Consequently EL₁, the first level of the extended low hierarchy, is not closed under join.

Keywords: computational complexity, diagonalization, extended hierarchies, relativization

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.

Keyword: valued constraint satisfaction problems, expressive power, max-closed constraints, theory of computation

In this paper, we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases, a large class of valued constraints, of all possible arities, can be expressed by using valued constraints over the same domain of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.

Keywords: valued constraint satisfaction, expressibility, max-closed cost functions, polymorphisms, feasibility polymorphisms, fractional polymorphisms

A variable elimination rule allows the polynomial time identification of certain variables whose elimination does not affect the satisfiability of an instance. Variable elimination in the constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible patterns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel.

Keywords: constraint satisfaction, tractability, arc consistency, forbidden pattern

Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary size.

We show that every core language Γ either admits a binary idempotent and symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ). In other words, there is a single algorithm for all tractable cases and a single reason for intractability. Our results show that for exact solvability of VCSPs the basic linear programming relaxation suffices and semidefinite relaxations do not add any power. The proof idea uses a variation of Motzkin's Transposition Theorem, hyperplane arrangements, and a technique recently introduced by Kolmogorov [arXiv:1207.7213] reformulated using Markov chains.

Our results generalise all previous partial classifications of finite-valued languages: the classifications of {0,1}-valued languages on two-element, three-element, and four-element domains obtained by Creignou [JCSS'95], Jonsson et al. [SICOMP'06], and Jonsson et al. [CP'11], respectively; the classification of {0,1}-valued languages containing all unary functions obtained by Deineko et al. [JACM'06]; the classifications of finite-valued languages on two-element and three-element domains obtained by Cohen et al. [AIJ'06] and Huber et al. [SODA'13], respectively; the classification of finite-valued languages containing all {0,1}-valued unary functions obtained by Kolmogorov and Živný [SODA'12]; and the classification of Min-0-Ext problems obtained recently by Hirai [SODA'13].

Keywords: discrete optimisation, complexity, valued constraint satisfaction problems, dichotomy

A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).

Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation. Using this result, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree- submodular on arbitrary trees.

Keywords: valued constraint satisfaction, fractional polymorphisms, fractional homomorphisms, submodularity, bisubmodularity, linear programming

Tractable classes of binary CSP and binary Max-CSP have recently been discovered by studying classes of instances defined by excluding subproblems. In this paper we characterise the complexity of all classes of binary Max-CSP instances defined by forbidding a single subproblem. In the resulting dichotomy, the only non-trivial tractable class defined by a forbidden subproblem corresponds to the set of instances satisfying the so-called joint-winner property.

Keywords: complexity, dichotomy, Max-CSP, subproblems

NB: The preprint corrects typos in Definition 1 and Lemma 3 in the publisher's version.

Boolean satisfiability (SAT) solvers have improved enormously in performance over the last 10-15 years and are today an indispensable tool for solving a wide range of computational problems. However, our understanding of what makes SAT instances hard or easy in practice is still quite limited. A recent line of research in proof complexity has studied theoretical complexity measures such as length, width, and space in resolution, which is a proof system closely related to state-of-the-art confliict-driven clause learning (CDCL) SAT solvers. Although it seems like a natural question whether these complexity measures could be relevant for understanding the practical hardness of SAT instances, to date there has been very limited research on such possible connections. This paper sets out on a systematic study of the interconnections between theoretical complexity and practical SAT solver performance. Our main focus is on space complexity in resolution, and we report results from extensive experiments aimed at understanding to what extent this measure is correlated with hardness in practice. Our conclusion from the empirical data is that the resolution space complexity of a formula would seem to be a more fine-grained indicator of whether the formula is hard or easy than the length or width needed in a resolution proof. On the theory side, we prove a separation of general and tree-like resolution space, where the latter has been proposed before as a measure of practical hardness, and also show connections between resolution space and backdoor sets

Keywords: backdoors, proof complexity, SAT solvers, resolution

We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well-understood, see Raghavendra [STOC'08]. However, there is no characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimisation perspective.

We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0,∞}-valued cost functions (i.e. relations), such languages have been called conservative and studied by Bulatov [LICS'03] and recently by Barto [LICS'11]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [AIJ'06] for languages over Boolean domains, by Deineko et al. [JACM'08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [STACS'10] for {0,∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom).

We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains is significantly harder than the Boolean case. The polynomial-time algorithm we present for the tractable cases is a generalisation of the submodular minimisation problem and a result of Cohen et al. [TCS'08].

Our results generalise previous results by Takhanov [STACS'10] and (a subset of results) by Cohen et al. [AIJ'06] and Deineko et al. [JACM'08]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [JACM'08], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.

Keywords: complexity, dichotomy, discrete optimisation, multimorphisms, submodularity, valued constraint satisfaction problems

The connection between the complexity of constraint languages and clone theory, discovered by Cohen and Jeavons in a series of papers, has been a fruitful line of research on the complexity of CSPs. In a recent result, Cohen et al. [MFCS'11] have established a Galois connection between the complexity of valued constraint languages and so-called weighted clones. In this paper, we initiate the study of weighted clones. Firstly, we prove an analogue of Rosenberg's classification of minimal clones for weighted clones. Secondly, we show minimality of several weighted clones whose support clone is generated by a single minimal operation. Finally, we classify all Boolean weighted clones. This classification implies a complexity classification of Boolean valued constraint languages obtained by Cohen et al. [AIJ'06].

Keywords: complexity, minimal weighted clones, weighted polymorphisms, classification of boolean valued constraint satisfaction problems

We study the computational complexity of binary valued constraint satisfaction problems (VCSP) given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, including CSP, Max-CSP, finite-valued VCSP, and general-valued VCSP, the only non-trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property [AIJ'11].

Keywords: constraint satisfaction, dichotomy, hybrid tractability, valued constraint satisfaction problems

We introduce tractable classes of VCSP instances based on convex cost functions. Firstly, we show that the class of VCSP instances satisfying the hierarchically nested convexity property is tractable. This class generalises our recent results on VCSP instances satisfying the non-overlapping convexity property by dropping the assumption that the input functions are non-decreasing [AIJ'11]. Not only do we generalise the tractable class from [AIJ'11], but also our algorithm has better running time compared to the algorithm from [AIJ'11]. We present several examples of applications including soft hierarchical global cardinality constraints, useful in rostering problems. We go on to show that, over Boolean domains, it is possible to determine in polynomial time whether there exists some subset of the constraints such that the VCSP satisfies the hierarchically nested convexity property after renaming the variables in these constraints.

Keywords: constraint optimisation, hybrid tractability, valued constraint satisfaction problems, convex functions, hierarchically nested structures

The complexity of any optimisation problem depends critically on the form of the objective function. Valued constraint satisfaction problems are discrete optimisation problems where the function to be minimised is given as a sum of cost functions defined on specified subsets of variables. These cost functions are chosen from some fixed set of available cost functions, known as a valued constraint language. We show in this paper that when the costs are non-negative rational numbers or infinite, then the complexity of a valued constraint problem is determined by certain algebraic properties of this valued constraint language, which we call weighted polymorphisms. We define a Galois connection between valued constraint languages and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach in the search for tractable valued constraint languages.

Keywords: Galois connection, valued constraint satisfaction problems, constraint optimisation, weighted polymorphisms, weighted clones.

The constraint satisfaction problem (CSP) is a central generic problem in artificial intelligence. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this paper we study hybrid tractability of soft constraint problems; that is, properties which guarantee tractability of the given soft constraint problem, but properties which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of soft constraints in the instance (such as submodularity).

We firstly present two hybrid classes of soft constraint problems defined by forbidden subgraphs in the structure of the instance. These classes allow certain combinations of binary crisp constraints together with arbitrary unary soft constraints.

We then introduce the joint-winner property, which allows us to define a novel hybrid tractable class of soft constraint problems with soft binary and unary constraints. This class generalises the SoftAllDiff constraint with arbitrary unary soft constraints. We show that the joint-winner property is easily recognisable in polynomial time and present a polynomial-time algorithm based on maximum-flows for the class of soft constraint problems satisfying the joint-winner property. Moreover, we show that if cost functions can only take on two distinct values then this class is maximal.

Keywords: constraint optimisation, tractability, joint-winner property, valued constraint satisfaction problems

The AllDifferent constraint was one of the first global constraints [AAAI'94] and it enforces the conjunction of one binary constraint, the not-equal constraint, for every pair of variables. By looking at the set of all pairwise not-equal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global Same-Relation constraints and show that AllDifferent is a huge exception: most Same-Relation Constraints pose NP-hard filtering problems.

Keywords: AllDifferent, same-relation constraint, tractable GAC

The Valued Constraint Satisfaction Problem (VCSP) is a general framework encompassing many optimisation problems. We discuss precisely what it means for a problem to be modelled in the VCSP framework. Using our analysis, we show that some optimisation problems, such as (s,t)-Min-Cut and Submodular Function Minimisation can be modelled using a restricted set of valued constraints which are tractable to solve regardless of how they are combined. Hence, these problems can be viewed as special cases of more general problems which include all possible instances using the same forms of valued constraint. However, other, apparently similar, problems such as Min-Cut and Symmetric Submodular Function Minimisation, which also have polynomial-time algorithms, can only be naturally modelled in the VCSP framework by using valued constraints which can represent NP-complete problems. This suggests that the reason for tractability in these problems is more subtle; it relies not only on the form of the valued constraints, but also on the precise structure of the problem. Furthermore, our results suggest that allowing constant constraints can significantly alter the complexity of problems in the VCSP framework, in contrast to the CSP framework.

Keywords: valued constraint satisfaction, modelling, power of constant constraints

We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.

Our results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

Keywords: decomposition of submodular functions, min-cut, pseudo-Boolean optimisation, submodular function minimisation.

Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems VCSP. It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n⁶) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. We also discuss the question of whether all submodular constraints of bounded arity over a Boolean domain are expressible using only binary submodular constraints, and can therefore be minimised efficiently.

Keywords: valued constraint satisfaction problems, submodular constraints, minimisation of submodular functions, min-cut, pseudo-Boolean optimisation

In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.

Keywords: valued constraint satisfaction, expressibility, max-closed cost functions, polymorphisms, feasibility polymorphisms, fractional polymorphisms

This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows a variety of combinatorial optimisation problems to be described. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation or Markov Random Fields.

We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraints in terms of certain algebraic properties, and extend this result by showing a new connection between the expressive power of valued constraints and linear programming. We prove a decidability result for related algebraic properties.

We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We also present a full classification of various classes of constraints with respect to this problem.

We then study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively.

These results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.