Virtual Pairwise Consistency in Cost Function Networks

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Virtual Pairwise Consistency in Cost Function Networks

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Virtual Pairwise Consistency in Cost Function Networks

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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 statě ve sborníku

Integration of Constraint Programming, Artificial Intelligence, and Operations Research

ISBN

978-3-031-33270-8

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

10

Strana od-do

417-426

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Basel

Místo konání akce

Nice

Datum konání akce

29. 5. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—