Using a Choice Function for Guiding Enumeration in Constraint Solving

摘要

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