License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.23
URN: urn:nbn:de:0030-drops-153149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15314/
Go to the corresponding LIPIcs Volume Portal

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

Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations

pdf-format:
LIPIcs-CP-2021-23.pdf (1.0 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2021/15314},
  URN =		{urn:nbn:de:0030-drops-153149},
  doi =		{10.4230/LIPIcs.CP.2021.23},
  annote =	{Keywords: Weighted CSP, Super-Reparametrization, Linear Programming, Constraint Propagation}
}

Keywords: Weighted CSP, Super-Reparametrization, Linear Programming, Constraint Propagation
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI