Project Leaders                                                                                                                  francais

David Avis and Kazuo Iwama

Principal members:

Kyoto:      Marco Cuturi, Satoru Iwata, Naoki Katoh, Hiroshi Nagamochi, Shin-ichi Tanigawa

Montreal: Miguel Anjos, Guyslain Naves, Bruce Reed, Bruce Shepherd

Objectives:

-  To combine the research efforts of two major research groups in discrete optimization, one in Kyoto and one in Montreal.
-  To solve concrete problems, contributing to the training of young researchers in computer science and optimization.

Events:

January-April 2012. Project start-up. Working group on computing a Nash equilibrium and on evacuation models.

Location: GERAD                 Organizers : M. Anjos et D. Avis

Project summary :

 Discrete optimization is a branch of computer science and applied mathematics which has shown remarkable theoretical and practical development in recent years. It combines the techniques of combinatorial analysis, linear programming and the theory of algorithms with the goal of solving optimization problems with discrete decision variables. We will consider the five subprojects below:

1.      Evacuation models

2.      Efficient generation of molecules in  biology and chemistry

3.      Generation of a Nash equilibrium by the primal-dual interior point method

4.      Application of polyhedral computation to machine learning

5.      Discrete muliflows in networks

Project Financing :    N.S.E.R.C.  and   J.S.P.S.