DROPS

Document

DOI: 10.4230/LIPIcs.CP.2021.23

Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations

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

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{dlask_et_al:LIPIcs.CP.2021.23,
  author =	{Dlask, Tom\'{a}\v{s} and Werner, Tom\'{a}\v{s} and de Givry, Simon},
  title =	{{Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.23},
  URN =		{urn:nbn:de:0030-drops-153149},
  doi =		{10.4230/LIPIcs.CP.2021.23},
  annote =	{Keywords: Weighted CSP, Super-Reparametrization, Linear Programming, Constraint Propagation}
}

Search Results

Documents authored by Dlask, Tomáš

Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations

Abstract

Cite as

Thanks for your feedback!

Could not send message