research-article

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

Authors:

Manuel Bodirsky,

Marcello Mamino,

Caterina ViolaAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 23, Issue 1

Article No.: 7, Pages 1 - 35

https://doi.org/10.1145/3488721

Published: 22 November 2021 Publication History

Abstract

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

References

[1]

N. Bansal, A. Blum, and S. Chawla. 2004. Correlation clustering. Mach. Learn. 56, 1–3 (2004), 89–113.

Digital Library

[2]

Manuel Bodirsky and Martin Grohe. 2008. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’08), Lecture Notes in Computer Science, Luca Aceto, Ivan Damgard, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz (Eds.). Springer Verlag, 184 –196.

Digital Library

[3]

Manuel Bodirsky, Dugald Macpherson, and Johan Thapper. 2013. Constraint satisfaction tractability from semi-lattice operations on infinite sets. Trans. Comput. Logic 14, 4 (2013), 1–30.

Digital Library

[4]

Manuel Bodirsky and Marcello Mamino. 2018. Tropically convex constraint satisfaction. Theory Comput. Syst. 62, 3 (2018), 481–509.

Digital Library

[5]

Manuel Bodirsky, Marcello Mamino, and Caterina Viola. 2018. Submodular functions and valued constraint satisfaction problems over infinite domains. In Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL’18). 12:1–12:22.

[6]

Stephen P. Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.

[7]

Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17). 319–330.

[8]

David A. Cohen, Martin C. Cooper, Peter G. Jeavons, and Andrei A. Krokhin. 2006. The complexity of soft constraint satisfaction. Artif. Intell. 170, 11 (2006), 983–1016.

Digital Library

[9]

Jeanne Ferrante and Charles Rackoff. 1975. A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4, 1 (1975), 69–76.

Digital Library

[10]

Satoru Fujishige. 2005. Submodular Functions and Optimization (2nd ed.). North-Holland, Amsterdam.

[11]

M. Grötschel, L. Lovász, and L. Schrijver. 1994. Geometric Algorithms and Combinatorial Optimization (2nd ed.). Springer, Heidelberg.

[12]

Wilfrid Hodges. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge.

Digital Library

[13]

J. L. W. V. Jensen. 1906. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math. 30, 1 (01 Dec 1906), 175–193.

[14]

Peter Jonsson, Fredrik Kuivinen, and Johan Thapper. 2011. Min CSP on four elements: Moving beyond submodularity. In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP’11). 438–453.

Digital Library

[15]

Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. 2015a. The complexity of general-valued CSPs. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15). 1246–1258.

Digital Library

[16]

Vladimir Kolmogorov, Johan Thapper, and Stanislav Zivny. 2015b. The power of linear programming for general-valued CSPs. SIAM J. Comput. 44, 1 (2015), 1–36.

Digital Library

[17]

Marcin Kozik and Joanna Ochremiak. 2015. Algebraic properties of valued constraint satisfaction problem. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming ICALP’15). 846–858.

[18]

Gábor Kun and Mario Szegedy. 2009. A new line of attack on the dichotomy conjecture. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09). ACM, New York, NY, 725–734.

Digital Library

[19]

Alexander Schrijver. 1998. Theory of Linear and Integer Programming. Wiley Interscience Series in Discrete Mathematics and Optimization. Wiley, New York, NY.

Digital Library

[20]

Johan Thapper and Stanislav Živný. 2012. The power of linear programming for valued CSPs. In Proceedings of the IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). IEEE Computer Society, 669–678.

Digital Library

[21]

Johan Thapper and Stanislav Zivny. 2013. The complexity of finite-valued CSPs. In Proceedings of the Symposium on Theory of Computing Conference (STOC’13). 695–704.

Digital Library

[22]

Lou van den Dries. 1998. Tame Topology and O-minimal Structures. London Mathematical Society Lecture Note Series, Vol. 248. Cambridge University Press, Cambridge.

[23]

Dmitriy Zhuk. 2017. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17). 331–342.

Cited By

Bodirsky MSemanišinová ŽLutz CSobocinski PLago UEsparza J(2024)The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662071(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662071

Index Terms

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity theory and logic
  2. Logic

Recommendations

The Power of Linear Programming for Valued CSPs
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

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. An instance of the problem is specified by a sum of cost functions from the language with the ...
The Power of Linear Programming for General-Valued CSPs

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 ...
The complexity of conservative valued CSPs

We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 23, Issue 1

January 2022

237 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/3487995

Editor:
Anuj Dawar
University of Cambridge, United Kingdom

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 November 2021

Accepted: 01 September 2021

Revised: 01 July 2021

Received: 01 December 2019

Published in TOCL Volume 23, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

European Research Council (ERC)
European Union’s Horizon 2020
DFG Graduiertenkolleg 1763 (QuantLA)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bodirsky MSemanišinová ŽLutz CSobocinski PLago UEsparza J(2024)The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662071(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662071

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents