Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41802
Title: Search space reduction and russian doll search
Authors: Cheng, K.C.K.
Yap, R.H.C. 
Issue Date: 2007
Source: 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.

Page view(s)

63
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.