Abstract: 
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. Finitevalued constraint languages contain functions that take on rational costs and generalvalued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises wellstudied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (MaxCSPs).
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 generalvalued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finitevalued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel and previously widelyopen classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as ksubmodular) on arbitrary finite domains; (3) weakly (and hence strongly) treesubmodular on arbitrary trees.
