Back

Session MB10 - Programmation par contraintes : recherche heuristique / Constraint Programming: Heuristic Search

Day Monday, May 04, 2009
Room Dutailier International
President Gilles Pesant

Presentations

03h30 PM-
03h55 PM
Parallelizing Global Constraint
  Simon Boivin, École Polytechnique de Montréal, Génie Informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Bernard Gendron, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, Québec, Canada
Gilles Pesant, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

Parallel computers are ubiquitous in research and development environments in academia and in industry. In this presentation, we introduce parallel computing into the global constraints filtering procedures used in Constraint Programming. The parallel filtering algorithm for the Regular and the ListColoring global constraints will be discussed. Scalability tests that show the advantages and the disadvantages will be presented.


03h55 PM-
04h20 PM
Generic Heuristic Search using the EMBP Framework
  Ronan Le Bras, École Polytechnique de Montréal, Département de génie informatique et génie logiciel
Alessandro Zanarini, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Gilles Pesant, École Polytechnique de Montréal, Département de génie informatique et génie logiciel, C.P. 6079 Succ Centre Ville, Montreal, Quebec, Canada, H3C 3A7

Accurately estimating the distribution of solutions to a problem, should solutions exist, provides efficient search heuristics. The purpose of this paper is to propose new generic ways of computing such estimates, with different degrees of accuracy and complexity. We build on the Expectation-Maximization Belief-Propagation (EMPB) framework proposed by Hsu et al. (2007) to solve constraint satisfaction problems.


04h20 PM-
04h45 PM
Adaptive Discrepancy Search
  Gilles Pesant, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Jean-Marc Frayret, École Polytechnique de Montréal, mathématiques et génie industriel, Montréal, Québec, Canada
Jonathan Gaudreault, École Polytechnique de Montréal, Génie informatique, Qc, Canada

Previous results have shown that search strategies based on discrepancies (e.g. LDS) can be adapted to a distributed context. They are more effective than chronological backtracking in such setting. In this talk we introduce ADS, an adaptive strategy based on discrepancies. It enables the agents to collectively and dynamically learn which areas of the tree are most promising.


04h45 PM-
05h10 PM
An Experimental Analysis of Solution Counting Based Heuristics
  Alessandro Zanarini, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Gilles Pesant, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We present an experimental study of some variations of solution counting heuristics compared with the state-of-the-art of generic heuristics on 8 different combinatorial problems taken from the literature. We further analyze the heuristic behavior when integrated in a randomized restarts and/or quick shaving framework, showing an impressive performance gain for counting based heuristics.


Back