Let $D$, called the domain, be a fixed finite set and let $\Gamma$, called the valued constraint language, be a fixed set of functions of the form $f:D^m\to\mathbb{Q}\cup\{\infty\}$, where different functions might have different arity $m$. We study the valued constraint satisfaction problem parametrised by $\Gamma$, denoted by VCSP$(\Gamma)$. These are minimisation problems given by $n$ variables and the objective function given by a sum of functions from $\Gamma$, each depending on a subset of the $n$ variables. For example, if $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,\infty\}$-valued functions, VCSP($\Gamma$) corresponds to 3-SAT. More generally, if $\Gamma$ contains only $\{0,\infty\}$-valued functions, VCSP($\Gamma$) corresponds to CSP($\Gamma$). If $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,1\}$-valued functions, VCSP($\Gamma$) corresponds to Min-3-SAT, in which the goal is to minimise the number of unsatisfied clauses in a 3-CNF instance. Finite-valued constraint languages contain functions that take on only rational values and not infinite values.
Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a valued constraint language $\Gamma$, BLP is a decision procedure for $\Gamma$ if and only if $\Gamma$ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language $\Gamma$, BLP is a decision procedure if and only if $\Gamma$ admits a symmetric fractional polymorphism of some arity, or equivalently, if $\Gamma$ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel classes of problems, including problems over valued constraint
languages that are: (1) submodular on arbitrary lattices; (2)
$k$-submodular on arbitrary finite domains;
(3) weakly (and hence strongly) tree-submodular on arbitrary trees.