Using a choice function for guiding enumeration in constraint solving

Broderick Crawford, Carlos Castroy, Eric Monfroyyz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of Special Session - 9th Mexican International Conference on Artificial Intelligence
Subtitle of host publicationAdvances in Artificial Intelligence and Applications, MICAI 2010
Pages37-42
Number of pages6
DOIs
StatePublished - 2010
Externally publishedYes
Event9th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence and Applications, MICAI 2010 - Pachuca, Mexico
Duration: 8 Nov 201013 Nov 2010

Publication series

NameProceedings of Special Session - 9th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence and Applications, MICAI 2010

Conference

Conference9th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence and Applications, MICAI 2010
Country/TerritoryMexico
CityPachuca
Period8/11/1013/11/10

Keywords

  • Autonomous search
  • Constraint programming
  • Enumeration strategy
  • Variable ordering heuristic

Fingerprint

Dive into the research topics of 'Using a choice function for guiding enumeration in constraint solving'. Together they form a unique fingerprint.

Cite this