Retour

Séance MB9 - Programmation par contraintes II / Constraint Programming II

Jour lundi, le 7 mai 2007
Salle Rona
Président Gilles Pesant

Présentations

15h30-
15h55
Parallel Constraint Programming Based on a Discrepancies Based Search Decomposition
  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, CRT
Gilles Pesant, École Polytechnique de Montréal, CRT et Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We present a parallel constraint programming algorithm to solve the traveling tournament problem. The algorithm uses a heuristic ranking of the possible values of the variables based on the reduced costs obtained by solving a linear programming relaxation of an integer programming formulation of the problem. We use Discrepancy Based Search (DBS) to generate the best subproblems at the beginning of the search.


15h55-
16h20
Discrepancy-Based Search for Multi-Agent Optimization
  Jonathan Gaudreault, École Polytechnique de Montréal, Génie informatique, Qc
Jean-Marc Frayret, Université Laval, FOR@C Research Consortium, Network Technologies Research Center (CENTOR), Cité universitaire, Pavillon Adrien Pouliot, Québec, Québec, Canada, G1K 7P4
Gilles Pesant, École Polytechnique de Montréal, CRT et Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

Distributed Constraint Optimization is increasingly used to formalize problem solving by multiple agents. However, there are situations where agents represent an organization made up of heterogeneous agents (e.g. network of companies) in which the context, the structure, and the business rules define the interactions that are possible between them. The solution space for those hierarchical problems is reminiscent of the ones of centralized combinatorial problems. Therefore, we propose a distributed algorithm (MacDS) that performs a discrepancy-based search which is known to perform well for centralized problems. The proposed algorithm is complete and aims at producing good solutions in a short amount of time. It allows concurrent computation and is tolerant to message delays. It has been evaluated using real industrial problems with complex subproblems, for which it showed good performance.


16h20-
16h45
Decomposing Global Constraints
  Claude-Guy Quimper, University of Waterloo, School of Computer Science, Waterloo, Ontario, Canada, N2L 3G1
Toby Walsh, NICTA and University of New South Wales, School of Computer Science and Engineering, Locked Bag 6016, University of New South Wales, Kensington, NSW, Australia, 1466

We show how different global constraints can be decomposed into elementary constraints without hindering propagation. The use of a decomposition offers many advantages compare to the use of a monolithic propagator. We present the decomposition of the REGULAR, the GRAMMAR, and the SEQUENCE constraints as well as some decompositions of linear constraints.


16h45-
17h10
Approximated Counting Algorithms for the All-Different Constraint
  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, CRT et Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

Recent studies have shown the potential of counting-based heuristics in terms of easy-to-use and efficiency. The basic idea is to enrich the constraint inference framework in order not only to reduce the search space but also to guide the search towards area that are likely to contain an high number of solutions. Although preliminary results seem very promising, its applicability has to face some open issues such as efficient counting for the widely-used all-different constraint. In this talk, we will present the state-of-the-art of approximated counting algorithms for the all-different constraint. We will propose an improvement over one of the algorithms that seems to better suit our needs. Experimental results will show the effectiveness of our approach as well as its impact in a counting-based heuristic framework.


Retour