The power of linear programming for general-valued CSPs

Original · EN

Let D, called the domain, be a fixed finite set and let Γ, called the valued constraint language, be a fixed set of functions of the form f:Dᵐ∪{∞}, where different functions might have different arity m. We study the valued constraint satisfaction problem parametrised by Γ, denoted by VCSP(Γ). These are minimisation problems given by n variables and the objective function given by a sum of functions from Γ, each depending on a subset of the n variables. 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 Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued 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 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.