The power of linear programming for general-valued CSPs

Abstract

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. 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.

A full version of a FOCS'12 paper by the last two authors (arXiv:1204.1079) and an ICALP'13 paper by the first author (arXiv:1207.7213) to appear in SIAM Journal on Computing (SICOMP)

References in corpus (2)

• Lagrangian Relaxation for MAP Estimation in Graphical Models
• The Expressive Power of Binary Submodular Functions

Cited by in corpus (25)

• The power of Sherali-Adams relaxations for general-valued CSPs
• CLAP: A New Algorithm for Promise CSPs
• On k-Submodular Relaxation
• Necessary conditions for tractability of valued CSPs
• The limits of SDP relaxations for general-valued CSPs
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• L-convexity on graph structures
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• Sherali-Adams relaxations for valued CSPs
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• A Compact Representation for Modular Semilattices and its Applications
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective
• Computing DM-decomposition of a partitioned matrix with rank-1 blocks
• Binarisation for Valued Constraint Satisfaction Problems
• Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
• Point-width and Max-CSPs
• A polynomial-time algorithm for median-closed semilinear constraints
• A tractable class of binary VCSPs via M-convex intersection
• On a general framework for network representability in discrete optimization
• Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation
• On Planar Valued CSPs
• Hierarchies of Minion Tests for PCSPs through Tensors
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Using a min-cut generalisation to go beyond Boolean surjective VCSPs