Virtual Pairwise Consistency in Cost Function Networks

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00370962" target="_blank" >RIV/68407700:21230/23:00370962 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-33271-5_27" target="_blank" >https://doi.org/10.1007/978-3-031-33271-5_27</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-33271-5_27" target="_blank" >10.1007/978-3-031-33271-5_27</a>

Result language
angličtina
Original language name
Virtual Pairwise Consistency in Cost Function Networks
Original language description
In constraint satisfaction, pairwise consistency (PWC) is a well-known local consistency improving generalized arc consistency in theory but not often in practice. A popular approach to enforcing PWC enforces arc consistency on the dual encoding of the problem, allowing to reuse existing AC algorithms. In this paper, we explore the benefit of this simple approach in the optimization context of cost function networks and soft local consistencies. Using a dual encoding, we obtain an equivalent binary cost function network where enforcing virtual arc consistency achieves virtual PWC on the original problem. We experimentally observed that adding extra non-binary cost functions before the dual encoding results in even stronger bounds. Such supplementary cost functions may be produced by bounded variable elimination or by adding ternary zero-cost functions. Experiments on (probabilistic) graphical models, from the UAI 2022 competition benchmark, show a clear improvement when using our approach inside a branch-and-bound solver compared to the state-of-the-art.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Article name in the collection
Integration of Constraint Programming, Artiﬁcial Intelligence, and Operations Research
ISBN
978-3-031-33270-8
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
10
Pages from-to
417-426
Publisher name
Springer Nature Switzerland AG
Place of publication
Basel
Event location
Nice
Event date
May 29, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)