Domain - extra
Combinatorial Optimization
octobre 2011
Stochastic Combinatorial Optimization
Thesis advisor
Collaboration with Professor Imai from the Technology Institute of Tokyo
The research topic is Semidefinite Programming and Combinatorial Stochastic Optimization, which is at the crossroads between discrete mathematics, graph theory, optimization and computer science. The project aims at developing new and fast methods for finding exact or approximate solutions to hard combinatorial stochastic optimization problems. Semidefinite programming is a generalization of classic linear programming dealing with optimization problems over positive semidefinite matrices. Working on that and related topics may be part of the PhD research project, as well as algorithmic and computational studies to practical applications amongst all telecommunications network design problems, risk modelling in finance and electricity planning problems.
Semidefinite programming is a generalization of classic linear programming dealing with optimization problems over positive semidefinite matrices. Recently, there has been increasing interest in the use of semidefinite programming in solving combinatorial optimization problems. This started with the seminal work of Lovasz (1979) on the so-called theta function. This also led Grötchel, Lovasz and Schrijver (1981) to develop a polynomial time algorithm to solve the maximum stable set problem for perfect graphs. More recently, Goemens and Williamson (1995) improved approximation algorithms for the max cut and related problems using semidefinite programming.
Stochastic combinatorial optimization is a recent topic in optimization, and has met a little interest in the optimization and computer science commnities. This is especially due to grouping two difficult areas, namely combinatorial and stochastic optimization.
The objcetives are four fold:

1. Extend max-k-flow problems to multicommodity problems.

2. Derive semidefinite relaxations in order to build performant polynomial algorthms.

3. Consider the capacities of the edges as random variables, and apply 1. and 2. to the obtained stochastic combinatorial problems.

4. Apply the previous obtained results to survivable network design problems.
Work program
The main step correpond the 4 objectives described above.
Extra information
- Research master in computer science or applied mathematics
- Good knowledge of the operations research and probability/statistics fields
- Good programming skills (C, C++)
Télécharger Sujet de these 2011 Combinatorics.pdf
Expected funding
Institutional funding
Status of funding
Mr. Jean-François Baffier is our favourite candidate for this Ph.D work. Mr. Baffier is preparing his Master degree in Computer Science at the University of Paris Sud. He is preparing his master thesis in Japan under the supervision of Professor Imai in Combinatorial Optimization. He is expected to have an excellent combinatorial optimization education. He is an excellent student and has got very high score in the Master exams.
Vendredi 25 mars 2011 14:01:58 CET
dernière modif.
Dimanche 26 juin 2011 22:46:46 CEST

Fichiers joints

PhDprop_StochasticLS.odt 25 Mar 2011 14:1719529.64 Kb
PhDprop_StochasticLS.pdf 25 Mar 2011 14:24121385.81 Kb
Sujet de these 2011 Combinatorics.pdf 26 Jun 2011 22:3916012.78 Kb
Sujet de these 2011 Combinatorics.pdf 26 Jun 2011 22:39181112.78 Kb

Ecole Doctorale Informatique Paris-Sud

Nicole Bidoit
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps

ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à