Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00352206" target="_blank" >RIV/68407700:21230/21:00352206 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.CP.2021.23" target="_blank" >https://doi.org/10.4230/LIPIcs.CP.2021.23</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CP.2021.23" target="_blank" >10.4230/LIPIcs.CP.2021.23</a>
Alternative languages
Result language
angličtina
Original language name
Bounds on Weighted CSPs Using Constraint Propagation and Super-Reparametrizations
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
27th International Conference on Principles and Practice of Constraint Programming
ISBN
978-3-95977-211-2
ISSN
1868-8969
e-ISSN
—
Number of pages
18
Pages from-to
—
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
—
Event location
Montpellier (Virtual Conference)
Event date
Oct 25, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—