Ph.D
Group : Networking & Stochastic and Combinatorial Optimization
Fonctions sous modulaires stochastiques
Starts on 01/10/2008
Advisor : LISSER, Abdel
Funding : salarie
Affiliation : Université Paris-Saclay
Laboratory : LRI
Defended on 27/09/2013, committee :
Directeurs de thèse
M. Abdel Lisser, Professeur, Université Paris Sud.
Rapporteurs
M. Jean-Baptiste HIRIART-URRUTY, Professeur, Université de Toulouse.
M. Alexei GAIVORONSKI, Professeur, Université de Trondheim (Norvège).
Examinateurs
M. Marc BABOULIN, Professeur, Université Paris Sud.
M. Patrice PERNY, Professeur, Université Paris 6.
Research activities :
Abstract :
The global purpose of this thesis is to study the conditions to extend analytical and algebraical properties commonly observed in the resolution of deterministic combinatorial problems to the corresponding stochastic formulations of these problems. Two distinct situations are treated : discrete combinatorial stochastic problems and continuous stochastic problems.
Discrete situation is examined with the Two Stage formulation of the Maximum Weight Covering Forest. The well known corresponding deterministic formulation shows the connexions between the rank function of a matroid, the greedy algorithm , and the dual formulation. The discrete stochastic formulation of the Maximal Covering Forest is turned into a deterministic equivalent formulation, but, due to the number of scenarios, the associated dual is not complete. The work of this thesis leads to understand in which cases the dual formulation still has the same value as the primal integer formulation. Usually, classical combinatorial approaches aim to find particular configurations in the graph, as circuits, in order to handle possible reconfigurations. For example, slight modifications of the weights of the edges might change considerably the configuration of the Maximum Weight Covering Forest. This can be seen as an obstacle to handle pure combinatorial proofs. However, some global relevant quantities, like the global weight of the selected edges during the greedy algorithm, have a continuous variation in function of slight modifications. We introduce some functions in order to outline these continuous variations. And we state in which cases Primal integral problems have the same objective values as dual formulations. When it is not the case, we propose an approximation method and we examine the NP completeness of this problem.\
Continuous stochastic problems are presented with the stochastic Knapsack with chance constraint. Chance constraint and dual Lagrangian formulation are adapted in the case where the expected probability of not exceeding the knapsack capacity is close to $1$. The introduced model consists in items whose costs and rewards follow normal distributions. In our case, we try to apply direct gradient methods without reformulating the problem into geometrical terms. We detail convergence conditions of gradient based methods directly on the initial formulation. This part is illustrated with numerical tests on combinatorial instances and Branch and Bound evaluations on relaxed formulations.
