Document Open Access Logo

Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations

Authors Tomáš Dlask , Tomáš Werner , Simon de Givry

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.23.pdf
  • Filesize: 0.98 MB
  • 18 pages

Document Identifiers

Author Details

Tomáš Dlask
  • Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic
Tomáš Werner
  • Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic
Simon de Givry
  • Université Fédérale de Toulouse, ANITI, INRAE, UR 875, France

Funding

  • Dlask, Tomáš: Supported by the Czech Science Foundation (grant 19-09967S) and the Grant Agency of the Czech Technical University in Prague (grant SGS19/170/OHK3/3T/13).
  • Werner, Tomáš: Supported by the Czech Science Foundation (grant 19-09967S) and the OP VVV project CZ.02.1.01/0.0/0.0/16_019/0000765.
  • de Givry, Simon: Supported by the "Agence nationale de la Recherche" (ANR-19-PIA3-0004 ANITI).

Cite AsGet BibTex

Tomáš Dlask, Tomáš Werner, and Simon de Givry. Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.23

Abstract

We propose a framework for computing upper bounds on the optimal value of the (maximization version of) Weighted CSP (WCSP) using super-reparametrizations, which are changes of the weights that keep or increase the WCSP objective for every assignment. We show that it is in principle possible to employ arbitrary (under certain technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. Newly, we implemented the method for singleton arc consistency (SAC) and compared it to other strong local consistencies in WCSPs on a public benchmark. The results show that the bounds obtained from SAC are superior for many instance groups.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Linear programming
  • Theory of computation → Linear programming
  • Theory of computation → Constraint and logic programming
Keywords
  • Weighted CSP
  • Super-Reparametrization
  • Linear Programming
  • Constraint Propagation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dhruv Batra, Sebastian Nowozin, and Pushmeet Kohli. Tighter relaxations for MAP-MRF inference: A local primal-dual gap based separation algorithm. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 146-154, 2011. Google Scholar
  2. Christian Bessiere, Stephane Cardon, Romuald Debruyne, and Christophe Lecoutre. Efficient algorithms for singleton arc consistency. Constraints, 16(1):25-53, 2011. Google Scholar
  3. Christian Bessiere and Romuald Debruyne. Theoretical analysis of singleton arc consistency. In Workshop on Modelling and Solving Problems with Constraints, pages 20-29, 2004. Google Scholar
  4. Martin C. Cooper. Cyclic consistency: a local reduction operation for binary valued constraints. Artificial Intelligence, 155(1-2):69-92, 2004. Google Scholar
  5. Martin C. Cooper, Simon de Givry, Martí Sanchez, Thomas Schiex, Matthias Zytnicki, and Tomáš Werner. Soft arc consistency revisited. Artificial Intelligence, 174(7-8):449-478, 2010. Google Scholar
  6. Martin C. Cooper, Simon de Givry, and Thomas Schiex. Optimal soft arc consistency. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, volume 7, pages 68-73, 2007. Google Scholar
  7. Martin C. Cooper, Marie de Roquemaurel, and Pierre Régnier. A weighted CSP approach to cost-optimal planning. AI Communications, 24(1):1-29, 2011. Google Scholar
  8. https://forgemia.inra.fr/thomas.schiex/cost-function-library, commit URL: https://forgemia.inra.fr/thomas.schiex/cost-function-library/-/tree/356bbb85764df58016e187ccc5d56c9426572450.
  9. Simon De Givry, Federico Heras, Matthias Zytnicki, and Javier Larrosa. Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. In IJCAI, volume 5, pages 84-89, 2005. Google Scholar
  10. Romuald Debruyne and Christian Bessiere. Some practicable filtering techniques for the constraint satisfaction problem. In Proceedings of IJCAI’97, pages 412-417, 1997. Google Scholar
  11. Tomáš Dlask. Minimizing convex piecewise-affine functions by local consistency techniques. Master’s Thesis, 2018. Google Scholar
  12. Tomáš Dlask and Tomáš Werner. Bounding linear programs by constraint propagation: Application to Max-SAT. In International Conference on Principles and Practice of Constraint Programming. Springer, 2020. Google Scholar
  13. Fabio Furini, Emiliano Traversi, Pietro Belotti, Antonio Frangioni, Ambros Gleixner, Nick Gould, Leo Liberti, Andrea Lodi, Ruth Misener, Hans Mittelmann, et al. QPLIB: a library of quadratic programming instances. Mathematical Programming Computation, 11(2):237-265, 2019. Google Scholar
  14. Amir Globerson and Tommi S Jaakkola. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In Advances in Neural Information Processing Systems, pages 553-560, 2008. Google Scholar
  15. Eric Grégoire, Bertrand Mazure, and Cédric Piette. On finding minimally unsatisfiable cores of CSPs. International Journal on Artificial Intelligence Tools, 17(04):745-763, 2008. Google Scholar
  16. Vladimir Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10):1568-1583, 2006. Google Scholar
  17. Nikos Komodakis and Nikos Paragios. Beyond loose LP-relaxations: Optimizing MRFs by repairing cycles. In European conference on computer vision, pages 806-820. Springer, 2008. Google Scholar
  18. V. K. Koval and M. I. Schlesinger. Dvumernoe programmirovanie v zadachakh analiza izobrazheniy (Two-dimensional programming in image analysis problems). Automatics and Telemechanics, 8:149-168, 1976. In Russian. Google Scholar
  19. Hiep Nguyen, Christian Bessiere, Simon de Givry, and Thomas Schiex. Triangle-based consistencies for cost function networks. Constraints, 22(2):230-264, 2017. Google Scholar
  20. Bogdan Savchynskyy. Discrete graphical models - an optimization perspective. Foundations and Trends in Computer Graphics and Vision, 11(3-4):160-429, 2019. Google Scholar
  21. M. Schlesinger. Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4(113-130):2, 1976. Google Scholar
  22. H. D. Sherali and W. P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal of Discrete Mathematics, 3(3):411-430, 1990. Google Scholar
  23. David Sontag and Tommi Jaakkola. Tree block coordinate descent for MAP in graphical models. In Artificial Intelligence and Statistics, pages 544-551, 2009. Google Scholar
  24. David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, and Yair Weiss. Tightening LP relaxations for MAP using message passing, 2008. Google Scholar
  25. URL: https://software.cs.uni-koeln.de/spinglass.
  26. URL: https://miat.inrae.fr/toulbar2.
  27. Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, and Bogdan Savchynskyy. MPLP++: Fast, parallel dual block-coordinate ascent for dense graphical models. In Proceedings of the European Conference on Computer Vision, pages 251-267, 2018. Google Scholar
  28. Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, and Bogdan Savchynskyy. Taxonomy of dual block-coordinate ascent methods for discrete energy minimization. In International Conference on Artificial Intelligence and Statistics, pages 2775-2785. PMLR, 2020. Google Scholar
  29. Stanislav Živný. The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies. Springer, 2012. Google Scholar
  30. Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1-305, 2008. Google Scholar
  31. Tomáš Werner. A linear programming approach to max-sum problem: A review. Technical Report CTU-CMP-2005-25, Center for Machine Perception, Czech Technical University, December 2005. Google Scholar
  32. Tomáš Werner. A linear programming approach to max-sum problem: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7):1165-1179, July 2007. Google Scholar
  33. Tomáš Werner. Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8):1474-1488, August 2010. Google Scholar
  34. Tomáš Werner. Marginal consistency: Upper-bounding partition functions over commutative semirings. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(7):1455-1468, July 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact