Exploiting tree decomposition and soft local consistency in weighted CSP - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2006

Exploiting tree decomposition and soft local consistency in weighted CSP

Abstract

Several recent approaches for processing graphical models (constraint and Bayesian networks) simultaneously exploit graph decomposition and local consistency enforcing. Graph decomposition exploits the problem structure and offers space and time complexity bounds while hard information propagation provides practical improvements of space and time behavior inside these theoretical bounds. Concurrently, the extension of local consistency to weighted constraint networks has led to important improvements in branch and bound based solvers. Indeed, soft local consistencies give incrementally computed strong lower bounds providing inexpensive yet powerful pruning and better informed heuristics. In this paper, we consider combinations of tree decomposition based approaches and soft local consistency enforcing for solving weighted constraint problems. The intricacy of weighted information processing leads to different approaches, with different theoretical properties. It appears that the most promising combination sacrifices a bit of theory for improved practical efficiency.
Fichier principal
Vignette du fichier
AAAI06-004.pdf (858.4 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-02755023 , version 1 (30-07-2020)

Identifiers

  • HAL Id : hal-02755023 , version 1
  • PRODINRA : 185353

Cite

Simon de Givry, Thomas Schiex, Gerard Verfaillie. Exploiting tree decomposition and soft local consistency in weighted CSP. Twenty-first National Conference on Artificial Intelligence - AAAI 2006, Jul 2006, Boston, United States. 1115 p. ⟨hal-02755023⟩
15 View
2 Download

Share

Gmail Facebook X LinkedIn More