Scientific Research and Essays

  • Abbreviation: Sci. Res. Essays
  • Language: English
  • ISSN: 1992-2248
  • DOI: 10.5897/SRE
  • Start Year: 2006
  • Published Articles: 2754

Full Length Research Paper

Hybrid strategies of enumeration in constraint solving

Eric Monfroy1,4*, Broderick Crawford1,2, Ricardo Soto2,3, and Fernando Paredes5        
1Departamento de Informática, Universidad Técnica Federico Santa María, Av. España 1680, Valparaíso, Chile. 2Pontificia Universidad Católica de Valparaíso, Chile. 3Universidad Autónoma de Chile, Chile. 4CNRS, LINA, Université de Nantes, France. 5Escuela de Ingeniería Industrial, Universidad Diego Portales, Santiago, Chile.
Email: [email protected]

  •  Accepted: 16 August 2011
  •  Published: 30 September 2011

Abstract

Enumeration strategies (that is, selection of a variable and a value of its domain) are crucial components of Constraint Programming: they significantly influence the performances of the solving process, sometimes of several orders of magnitude. In this paper, we propose to use Local Search in order to help and guide enumeration: we extend the usual variable selection strategies of constraint programming and we perform the value selection with respect to the results of some local search. The experimental results obtained are rather promising.

 

Key words: Constraint programming, local search, hybridization methods, heuristic search.

Abbreviation

CSP, Constraint satisfaction problem; LS, local search; TSP,travelling salesman problem