TY - JOUR
T1 - Boosting autonomous search for CSPs via skylines
AU - Soto, Ricardo
AU - Crawford, Broderick
AU - Palma, Wenceslao
AU - Galleguillos, Karin
AU - Castro, Carlos
AU - Monfroy, Eric
AU - Johnson, Franklin
AU - Paredes, Fernando
N1 - Publisher Copyright:
© 2015 Elsevier Inc. All rights reserved.
PY - 2015/7/1
Y1 - 2015/7/1
N2 - Solving constraint satisfaction problems via constraint programming involves the exploration of a search tree where the potential solutions are distributed. The exploration phase is essentially controlled by an enumeration strategy that decides the order in which variables and values are selected to verify its feasibility. This process is known to be quite important, indeed perfect enumerations can reach a solution without useless explorations. However, selecting good strategies in advance is quite hard as the effects along the search are often unpredictable. Autonomous search addresses this concern by proposing to replace on the fly bad-performing strategies by more promising ones. Strategies are selected from a quality rank which is generated in function of their performance on the current solving process. However, the ranking computation is commonly tuned by an optimizer that negatively impacts the performance of the whole resolution. In this paper, we propose a faster autonomous search approach by integrating a powerful database technique called skyline. This technique allows us to avoid the use of costly rank functions and optimizers, accelerating as a consequence the solving process. We report results where the skyline-based approach clearly competes with previously reported autonomous search frameworks as well as with classic and more sophisticated heuristics such as impact-based search and dom/wdeg.
AB - Solving constraint satisfaction problems via constraint programming involves the exploration of a search tree where the potential solutions are distributed. The exploration phase is essentially controlled by an enumeration strategy that decides the order in which variables and values are selected to verify its feasibility. This process is known to be quite important, indeed perfect enumerations can reach a solution without useless explorations. However, selecting good strategies in advance is quite hard as the effects along the search are often unpredictable. Autonomous search addresses this concern by proposing to replace on the fly bad-performing strategies by more promising ones. Strategies are selected from a quality rank which is generated in function of their performance on the current solving process. However, the ranking computation is commonly tuned by an optimizer that negatively impacts the performance of the whole resolution. In this paper, we propose a faster autonomous search approach by integrating a powerful database technique called skyline. This technique allows us to avoid the use of costly rank functions and optimizers, accelerating as a consequence the solving process. We report results where the skyline-based approach clearly competes with previously reported autonomous search frameworks as well as with classic and more sophisticated heuristics such as impact-based search and dom/wdeg.
KW - Combinatorial optimization
KW - Constraint satisfaction
KW - Hyperheuristic
KW - Skyline
UR - http://www.scopus.com/inward/record.url?scp=84961288171&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2015.01.035
DO - 10.1016/j.ins.2015.01.035
M3 - Article
AN - SCOPUS:84961288171
VL - 308
SP - 38
EP - 48
JO - Information Sciences
JF - Information Sciences
SN - 0020-0255
ER -