Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Keywords : ALGORITME
Document type :
Conference papers
Complete list of metadata
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Thursday, June 4, 2020 - 9:06:34 AM
Last modification on : Friday, November 18, 2022 - 4:13:10 AM


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



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⟩



Record views