Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00366166" target="_blank" >RIV/68407700:21230/23:00366166 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10601-023-09343-6" target="_blank" >https://doi.org/10.1007/s10601-023-09343-6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10601-023-09343-6" target="_blank" >10.1007/s10601-023-09343-6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

Popis výsledku v původním jazyce

The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. 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.

Název v anglickém jazyce

Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

Popis výsledku anglicky

The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Svazek periodika

28

Číslo periodika v rámci svazku

June

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

43

Strana od-do

277-319

Kód UT WoS článku

000988361500001

EID výsledku v databázi Scopus

2-s2.0-85159397356