The power of linear programming for general-valued CSPs

DOI10.1137/130945648MaRDI QIDQ5252658zbMATH OpenOpenAlexFDO

Authors Vladimir Kolmogorov, Johan Thapper, S. Zivny

Publication date 2 June 2015

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4219

zbMATH Keywords

bisubmodularityfractional polymorphismslinear programmingsubmodularityvalued constraint satisfaction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Linear programming (90C05) Combinatorial optimization (90C27)

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}omathbbQcupinfty$, 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.

Recommendations

• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The complexity of general-valued CSPs
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• An Algebraic Characterisation of Complexity for Valued Constraint
• An algebraic theory of complexity for discrete optimization.
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• Arc consistency for soft constraints
• Bisubmodular Function Minimization
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Colouring, constraint satisfaction, and complexity
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Conjunctive-query containment and constraint satisfaction
• Consistency in networks of relations
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Discrete convexity and polynomial solvability in minimum 0-extension problems (extended abstract)
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Graphical models, exponential families, and variational inference
• Half-integrality, LP-branching and FPT algorithms
• Hard constraint satisfaction problems have hard gaps at location 1
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 5937160 (Why is no real title available?)
• Linear programming, width-1 CSPs, and robust satisfaction
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Min CSP on four elements: moving beyond submodularity
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Networks of constraints: Fundamental properties and applications to picture processing
• On the algebraic structure of combinatorial problems
• On the complexity of submodular function minimisation on diamonds
• Robust satisfiability for CSPs: hardness and algorithmic results
• Robust satisfiability of constraint satisfaction problems
• Skew bisubmodularity and valued CSPs
• Soft arc consistency revisited
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Submodular function minimization
• Submodularity on a tree: unifying L^-convex and bisubmodular functions
• Synthesizing constraint expressions
• The approximability of constraint satisfaction problems
• The approximability of MAX CSP with fixed-value constraints
• The complexity of conservative valued CSPs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The complexity of valued constraint satisfaction
• The complexity of valued constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The expressive power of binary submodular functions
• The partial constraint satisfaction problem: Facets and lifting theorems
• Towards a characterization of constant-factor approximable min CSPs
• Towards minimizing k-submodular functions
• Tractability and learnability arising from algebras with few subpowers
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions

Cited in

(56)

• On a general framework for network representability in discrete optimization
• A compact representation for minimizers of k-submodular functions
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Computing DM-decomposition of a partitioned matrix with rank-1 blocks
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• A compact representation for modular semilattices and its applications
• Minimum 0-extension problems on directed metrics
• Piecewise linear valued constraint satisfaction problems with fixed number of variables
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• On planar valued CSPs
• On \(k\)-submodular relaxation
• Linear programming, width-1 CSPs, and robust satisfaction
• On a general framework for network representability in discrete optimization (extended abstract)
• A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
• Skew bisubmodularity and valued CSPs
• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• A Galois connection for valued constraint languages of infinite size
• Sherali-Adams relaxations for valued CSPs
• Necessary conditions for tractability of valued CSPs
• The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Discrete convex functions on graphs and their algorithmic applications
• A tractable class of binary VCSPs via M-convex intersection
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Hybrid tractable classes of constraint problems
• The complexity of valued CSPs
• The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• Submodular functions and valued constraint satisfaction problems over infinite domains
• scientific article; zbMATH DE number 7559417 (Why is no real title available?)
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Beyond Boolean surjective VCSPs
• Testing the Complexity of a Valued CSP Language
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• The complexity of general-valued CSPs
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
• The complexity of conservative valued CSPs
• Gauges, loops, and polynomials for partition functions of graphical models
• CLAP: A New Algorithm for Promise CSPs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Super-reparametrizations of weighted CSPs: properties and optimization perspective
• Generalized minimum 0-extension problem and discrete convexity
• Edge bipartization faster than \(2^k\)
• The complexity of resilience problems via valued constraint satisfaction problems
• Algebraic approach to approximation
• Semidefinite programming and linear equations vs. homomorphism problems
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Duality theory in linear optimization and its extensions -- formally verified
• The complexity of resilience problems via valued constraint satisfaction
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms

Describes a project that uses

Uses Software

• ToulBar2
• JBool

This page was built for publication: The power of linear programming for general-valued CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5252658)