INRIA - international

EQUIPE ASSOCIEE	MOCQUASIN
sélection	2008

Equipe-Projet INRIA : Dionysos (ex Armor)	Organisme étranger partenaire : Université de Montréal (département d'informatique et recherche opérationnelle)
Centre de recherche INRIA : Rennes- Bretagne Atlantique Thème INRIA : CommB	Pays : Canada

	Coordinateur français	Coordinateur étranger
Nom, Prénom	Tuffin, Bruno	L'Ecuyer, Pierre
Grade/statut	CR1	Professeur et Chaire de Recherche du Canada en Simulation et Optimisation Stochastique
Organisme d'appartenance (précisez le département et/ou le laboratoire)	INRIA Rennes- Bretagne Atlantique	Université de Montréal (département d'informatique et recherche opérationnelle)
Adresse postale	IRISA Campus Universitaire de Beaulieu 35042 Rennes Cedex	Département d'informatique et de recherche opérationnelle Université de Montréal C.P. 6128, Succ. Centre-Ville, Montréal (Québec), Canada, H3C 3J7
URL	http://www.irisa.fr/armor/lesmembres/Tuffin/Tuffin.htm	http://www.iro.umontreal.ca/~lecuyer/indexf.html
Téléphone	+33 (0) 2 99 84 74 94	+1 (514) 343-2143
Télécopie	+33 (0) 2 99 84 71 71	+1 (514) 343-5834
Courriel	btuffin@irisa.fr	lecuyer@iro.umontreal.ca

La proposition en bref

Titre de la thématique de collaboration :Monte Carlo et Quasi-Monte Carlo pour la simulation d'événements rares
Monte Carlo and Quasi-Monte Carlo for rare event simulation

Descriptif : La résolution de nombreux problèmes scientifiques nécessite de calculer des sommes, des intégrales, ou encore de résoudre des équations ou des problèmes d'optimisation. Les techniques de calcul direct sont très vite dépassées par la complexité des modèles, de même que les méthodes d'approximation issues de l'analyse numérique classique, surtout pour des problèmes de grande dimension. Les méthodes de Monte carlo sont des outils statistiques qui permettent d'évaluer de tels modèles. Ce sont des méthodes qui sont aujourd'hui indispensables dans des domaines aussi variés et différents que la finance, la mise au point de nouveaux microcomposants électroniques, la sismologie, les télécommunications, en ingénierie ou en physique, mais aussi en biologie, en sciences sociales, etc. Néanmoins, elles ont la réputation d'être lentes, c'est à dire de demander un temps de calcul important pour atteindre une précision souhaitée. L'objectif du projet est de travailler sur les techniques dites d'accélération. Le cadre typique auquel nous nous intéresserons est celui de la simulation d'événements rares pour laquelle l'apparition d'une unique occurence de l'événement peut demander un temps très long. Deux grandes familles de méthodes existent et demandent une "calibration" précise selon le problème étudié: l'échantillonnage préférentiel et le splitting. L'échantillonnage préférentiel consiste à changer la loi régissant le système, mais une nouvelle loi pour laquelle l'événement est moins rare; l'estimateur est alors multiplié par un facteur approprié pour le garder sans biais. Le splitting, lorsqu'on simule un processus, consiste à éliminer les trajectoires/estimations qui s'éloignent de l'événement rare et à clôner celles qui s'en rapprochent; là encore, on retrouve la bonne valeur en pondérant correctement chaque trajectoire. Dans les deux cas, la difficulté est de trouver les bonnes stratégies permettant d'obtenir un estimateur robuste quand la rareté augmente. Notre objectif est de construire des méthodes robustes, principalement pour des problèmes en télécommunication et en sûreté de fonctionnement. La combinaison avec les méthodes de quasi-Monte Carlo randomisées, plus rapides mais au cadre applicatif plus limité, est aussi un enjeu prometteur.

Présentation de l'Équipe Associée

1. Présentation du coordinateur étranger

Pierre L'Ecuyer est professeur au département d'Informatique et de Recherche Opérationnelle, à l'Université de Montréal. Il est titulaire d'une Chaire de recherche du Canada en simulation stochastique et optimisation. Il a obtenu son doctorat en recherche opérationnelle en 1983, à l'Université de Montréal. Il a plus de 180 publications, dont environ 90 articles de revues et chapitres de livres. Ses principaux intérêts de recherche sont la génération de nombres aléatoires, les méthodes quasi-Monte Carlo, l'amélioration de l'efficacité via la réduction de variance, l'analyse des sensibilités et l'optimisation des systèmes stochastiques à événements discrets, et la simulation à événements discrets en général. Il est actuellement éditeur associé pour ACM Transactions on Modeling and Computer Simulation, ACM Transactions on Mathematical Software, Statistical Computing, International Transactions in Operational Research, The Open Applied Mathematics Journal, and Cryptography and Communications. Il a obtenu de nombreux prix, dont la E. W. R. Steacie fellowship en 1995-97, une Killam fellowship en 2001-03, et est devenu un INFORMS Fellow en 2006.
Plus d'informations sont disponibles sur sa page web http://www.iro.umontreal.ca/~lecuyer, ainsi qu'un cv complet à http://www.iro.umontreal.ca/~lecuyer/cvf.pdf.

2. Historique de la collaboration

2.1. entre les équipes :

La collaboration entre le projet Dionysos (ex ARMOR) et Pierre L'Ecuyer a été initiée en 2002, lors d'une rencontre avec Bruno Tuffin à la conférence MCQMC (Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing). Des invitations courtes respectives ont été réalisées (Bruno Tuffin à Montréal en Mai 2003 et Juillet 2005, Pierre L'Ecuyer à Rennes en Avril 2004 et Avril 2006) afin d'initier la collaboration. Un séjour a aussi eu lieu dans le cadre de la collaboration FQNRT-INRIA 2006 entre le GERAD et L'IRISA (coordonateurs François Legland et Bruno Remillard). Le fait le plus marquant de la collaboration passée est cependant le séjour sabbatique effectué par Pierre L'Ecuyer entre Juillet 2006 et fin Juin 2007 (moins trois mois de retour à Montréal l'hiver) au sein du projet ARMOR. Cette collaboration a notamment déjà donné lieu à de nombreux articles conjoints entre les différentes équipes, que le projet permettra de poursuivre. Ce projet sera également d'une certaine manière une continuité aux travaux communs réalisés au sein de l'action de recherche coopérative (ARC) INRIA RARE (2006-2007), sur le développement de techniques de simulation d'événements rares, qui était coordonnée par Armor, et dont Pierre L'Ecuyer était membre pendant son séjour sabbatique (et qui a notamment permis à Gerardo Rubino de collaborer avec Pierre L'Ecuyer). Enfin, le projet permettra d'impliquer d'autres personnes des deux côtés: Katy Paroux qui vient d'arriver dans l'équipe Dionysos, ainsi que Fabian Bastin, qui vient d'être nommé Professeur adjoint au DIRO à l'Université Montréal, et les étudiants de l'équipe de simulation (jusqu'ici, Valérie Demers, pendant sa thèse de Doctorat, avait été la seule impliquée) ou associés à Dionysos.

Publications communes, soumises ou publiées

P. L'Ecuyer, J. Blanchet, B. Tuffin, P.W. Glynn. Asymptotic Robustness of Estimators in Rare-Event Simulation. Soumis à ACM Transactions on Modeling and Computer Simulation.
P. L'Ecuyer, C. Lecot and B. Tuffin. A Randomized Quasi-Monte Carlo Method for Markov Chains.Operations Research, To appear.
P.-T. de Boer, P. L'Ecuyer, G. Rubino, and B. Tuffin, Estimating the Probability of a Rare Event Over a Finite Horizon. In Proceedings of the 2007 Winter Simulation Conference, IEEE Press, 2007.
P. L'Ecuyer, B. Tuffin. Effective Approximation of Zero-Variance Simulation in a Reliability Setting. In Proceedings of the 2007 European Simulation and Modelling Conference (ESM'2007), St. Julian's, Malta, October 2007.
P. L'Ecuyer, V. Demers and B. Tuffin. Rare Events, Splitting, and Quasi-Monte Carlo. ACM Transactions on Modeling and Computer Simulation, Vol. 17, Num. 2, Article 9, 2007.
J. Blanchet, P. Glynn, P. L'Ecuyer, W. Sandmann, B. Tuffin. Asymptotic Robustness of Estimators in Rare-Event Simulation. In Proceedings of the 2007 INFORMS Simulation Society (I-Sim) Research Workshop, Fontainebleau, France, July 2007.
P. L'Ecuyer, V. Demers and B. Tuffin. Splitting for rare-event simulation. In Proceedings of the 2006 Winter Simulation Conference, La Marina del Rey, CA, December 2006.
P. L'Ecuyer and B. Tuffin. Splitting with Weight Windows to Control the Likelihood Ratio in Importance Sampling. In Proceeding of the first VALUETOOLS Conference, ACM Digital Library, Pisa, Italy, October 2006.
B. Tuffin, P. L'Ecuyer and W. Sandmann. Robustness Properties in Simulations of Highly Reliable Systems. In Proceedings of RESIM 2006, Bamberg, germany, October 2006.
V. Demers, P. L'Ecuyer and B. Tuffin. A Combination of Randomized Quasi-Monte Carlo with Splitting for Rare-Event Simulation.. In In Proceedings of the 2005 European Simulation and Modelling Conference (ESM'2005), SCS Press, Porto, Portugal, October 2005.
P. L'Ecuyer, C. Lecot, B. Tuffin. Quasi-Monte Carlo simulation of Markov chains with randomized copies of a two-dimensional highly-uniform point set. Sixth International Conference on Monte Carlo and quasi-Monte Carlo Methods, Juan-les-Pins, France June 2004, Springer-Verlag, 2005.

Conférences sur résumés

P. L'Ecuyer, C. Lecot and B. Tuffin. A New Randomized Quasi-Monte Carlo Approach for Markov Chains. INFORMS Applied Probability Conference, Ottawa, Canada, July 2005.
V. Demers, P. L'Ecuyer and B. Tuffin. Combining Randomized Quasi-Monte Carlo with Splitting for Rare-Event Simulation. Sixth International Conference on Monte Carlo and quasi-Monte Carlo Methods, Germany, August 2006.

2.2. entre l'INRIA et l'organisme partenaire :
Les deux équipes ont participé au programme FQNRT-INRIA de 2006 (et terminé) sur le simulation d'événements rares (voir La page de la DRI).

3. Impact :

3.1. Cette collaboration permettrait de faire perdurer l'implication du projet Dionysos sur la simulation d'événements rares (comme en témoigne l'augmentation de la liste de publications sur le sujet lors de la visite sabbatique de Pierre L'Ecuyer). Cette collaboration permettra aussi de maintenir le rayonnement international et la visibilité obtenus sur ce thème.

3.2. D'autres projets de l'INRIA sont très intéressés par la simulation d'événements rares : les membres de l'ARC RARE, ASPI (Rennes), Omega (Sophia-Antipolis et Nancy), MATHFI (Rocquencourt), ainsi que Pierre del Moral à Bordeaux, et pourront bénéficier des séjours de Pierre L'Ecuyer et de son équipe.

3.3. La collaboration entre les équipes a déjà été le moteur d'autres travaux communs impliquant des chercheurs prestigieux du domaine: Jose Blanchet (Harvard University) et Peter Glynn (Stanford University) notamment. Nous pensons maintenir et accentuer ses collaborations parallèles grâce à l'équipe associée.

4. Divers :

Rappelons que les partenaires ont été membres d'une l'action FQNRT-INRIA en 2006 (maintenant terminée). L'Université de Montréal prévoit de participer financièrement au projet via la Chaire de recherche de Pierre L'Ecuyer, à hauteur de 10K Euros.

ESTIMATION PROSPECTIVE DES CO-FINANCEMENTS
Organisme	Montant
Université de Montréal -- Chaire de recherche de Pierre L'Ecuyer	10K Euros
Total	10K Euros

ESTIMATION DES DÉPENSES		Montant
	Nombre	Accueil	Missions	Total
Chercheurs confirmés	5	7.5K Euros	10K Euros	17.5K Euros
Post-doctorants	1	2.5K Euros		2.5K Euros
Doctorants	3	2.5K Euros	2.5K Euros	2.5K Euros
Stagiaires	2	2.5K Euros		2.5K Euros
Autre (précisez) : Conférences		4K Euros		4K Euros
Total	8	19K Euros	12.5K Euros	31.5K Euros
		- total des co-financements		10K Euros
	Financement "Équipe Associée" demandé			21.5K Euros

Programme INRIA "Equipes Associées"

I. DEFINITION

Présentation de l'Équipe Associée

II. PREVISIONS 2008

Programme de travail

Budget prévisionnel 2008