Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inrae.fr/hal-02755023
Contributor : Migration Prodinra <>
Submitted on : Thursday, July 30, 2020 - 5:06:51 PM
Last modification on : Tuesday, March 16, 2021 - 3:44:15 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 10:02:22 AM

File

AAAI06-004.pdf
Publisher files allowed on an open archive

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

22

Files downloads

8