Virtual Pairwise Consistency in Cost Function Networks - Département MathNum Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Virtual Pairwise Consistency in Cost Function Networks

Résumé

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.
Fichier principal
Vignette du fichier
Montalbano23a.pdf (535.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY - Paternité

Dates et versions

hal-04024022 , version 1 (10-03-2023)

Identifiants

  • HAL Id : hal-04024022 , version 1

Citer

Pierre Montalbano, David Allouche, Simon De Givry, George Katsirelos, Tomáš Werner. Virtual Pairwise Consistency in Cost Function Networks. 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, May 2023, Nice, France. ⟨hal-04024022⟩
64 Consultations
25 Téléchargements

Partager

Gmail Facebook X LinkedIn More