Journées de l'optimisation 2009 Optimizations days

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.

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.

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.

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.