Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Russian doll search for solving constraint optimization problems

Abstract : If the Constraint Satisfaction framework has been extended to deal with Constraint Optimization problems, it appears that optimization is far more complex than satisfaction. One of the causes of the inefficiency of complete tree search methods, like Depth First Branch and Bound, lies in the poor quality of the lower bound on the global valuation of a partial assignment, even when using Forward Checking techniques. In this paper, we introduce the Russian Doll Search algorithm which replaces one search by n successive searches on nested subproblems (n being the number of problem variables), records the results of each search and uses them later, when solving larger subproblems, in order to improve the lower bound on the global valuation of any partial assignment. On small random problems and on large real scheduling problems, this algorithm yields surprisingly good results, which greatly improve as the problems get more constrained and the bandwidth of the used variable ordering diminishes.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.inrae.fr/hal-02766400
Déposant : Migration Prodinra <>
Soumis le : jeudi 4 juin 2020 - 09:06:34
Dernière modification le : vendredi 12 juin 2020 - 11:32:20

Identifiants

  • HAL Id : hal-02766400, version 1
  • PRODINRA : 136084

Collections

Citation

G. Verfaillie, M. Lemaitre, Thomas Schiex. Russian doll search for solving constraint optimization problems. National American Conference on Artificial Intelligence, 1996, Portland, United States. ⟨hal-02766400⟩

Partager

Métriques

Consultations de la notice

3