TY - GEN
T1 - Using a choice function for guiding enumeration in constraint solving
AU - Crawford, Broderick
AU - Castroy, Carlos
AU - Monfroyyz, Eric
PY - 2010
Y1 - 2010
N2 - In Constraint Programming, selection of a variable and a value of its domain enumeration strategies are crucial for resolution performances.We propose to use a Choice Function for guiding enumeration: we exploit search process features to dynamically adapt a Constraint Programming solver in order to more efficiently solve Constraint Satisfaction Problems. The Choice Function provides guidance to the solver by indicating which enumeration strategy should be applied next based upon the information of the search process, it should be captured through some indicators. The Choice Function is defined as a weighted sum of indicators expressing the recent improvement produced by the enumeration strategy had been called. The weights are determined by a Genetic Algorithm in a multilevel approach. We report results where our combination of strategies outperforms the use of individual strategies.
AB - In Constraint Programming, selection of a variable and a value of its domain enumeration strategies are crucial for resolution performances.We propose to use a Choice Function for guiding enumeration: we exploit search process features to dynamically adapt a Constraint Programming solver in order to more efficiently solve Constraint Satisfaction Problems. The Choice Function provides guidance to the solver by indicating which enumeration strategy should be applied next based upon the information of the search process, it should be captured through some indicators. The Choice Function is defined as a weighted sum of indicators expressing the recent improvement produced by the enumeration strategy had been called. The weights are determined by a Genetic Algorithm in a multilevel approach. We report results where our combination of strategies outperforms the use of individual strategies.
KW - Autonomous search
KW - Constraint programming
KW - Enumeration strategy
KW - Variable ordering heuristic
UR - http://www.scopus.com/inward/record.url?scp=79951796585&partnerID=8YFLogxK
U2 - 10.1109/MICAI.2010.23
DO - 10.1109/MICAI.2010.23
M3 - Conference contribution
AN - SCOPUS:79951796585
SN - 9780769542843
T3 - Proceedings of Special Session - 9th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence and Applications, MICAI 2010
SP - 37
EP - 42
BT - Proceedings of Special Session - 9th Mexican International Conference on Artificial Intelligence
T2 - 9th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence and Applications, MICAI 2010
Y2 - 8 November 2010 through 13 November 2010
ER -