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
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Thursday, July 30, 2020 - 5:06:51 PM
Last modification on : Thursday, March 17, 2022 - 1:44:02 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 10:02:22 AM


Publisher files allowed on an open archive


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



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⟩



Record views


Files downloads