Please use this identifier to cite or link to this item:
|Title:||Search space reduction and russian doll search||Authors:||Cheng, K.C.K.
|Issue Date:||2007||Citation:||Cheng, K.C.K.,Yap, R.H.C. (2007). Search space reduction and russian doll search. Proceedings of the National Conference on Artificial Intelligence 1 : 179-184. ScholarBank@NUS Repository.||Abstract:||In a constraint optimization problem (COP), many feasible valuations lead to the same objective value. This often means a huge search space and poor performance in the propagation between the objective and problem variables. In this paper, we propose a different modeling and search strategy which focuses on the cost function. We show that by constructing a dual model on the objective variables, we can get strong propagation between the objective variables and the problem variables which allows search on the objective variables. We explain why and when searching on the objective variables can lead to large gains. We present a new Russian Doll Search algorithm, ORDS, which works on objective variables with dynamic variable ordering. Finally, we demonstrate using the hard Still-Life optimization problem the benefits of changing to the objective function model and ORDS. Copyright ©2007, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.||Source Title:||Proceedings of the National Conference on Artificial Intelligence||URI:||http://scholarbank.nus.edu.sg/handle/10635/41802||ISBN:||1577353234|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 19, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.