Russian doll search with tree decomposition - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Russian doll search with tree decomposition

Résumé

Optimization in graphical models is an important problem which has been studied in many AI frameworks such as weighted CSP, maximum satisfiability or probabilistic networks. By identifying conditionally independent subproblems, which are solved independently and whose optimum is cached, recent Branch and Bound algorithms offer better asymptotic time complexity. But the locality of bounds induced by decomposition often hampers the practical effects of this result because subproblems are often uselessly solved to optimality. Following the Russian Doll Search (RDS) algorithm, a possible approach to overcome this weakness is to (inductively) solve a relaxation of each subproblem to strengthen bounds. The algorithm obtained generalizes both RDS and treedecomposition based algorithms such as BTD or AND-OR Branch and Bound. We study its efficiency on different problems, closing a very hard frequency assignment instance which has been open for more than 10 years.
Fichier principal
Vignette du fichier
Russian doll search with tree decomposition_1.pdf (727.44 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02755904 , version 1 (03-06-2020)

Identifiants

  • HAL Id : hal-02755904 , version 1
  • PRODINRA : 187829
  • WOS : 000283727900095

Citer

Marti Sanchez, David Allouche, Simon de Givry, Thomas Schiex. Russian doll search with tree decomposition. 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, United States. pp.6. ⟨hal-02755904⟩
30 Consultations
15 Téléchargements

Partager

Gmail Facebook X LinkedIn More