Date : 2008
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Langue / Language : anglais / English
Systèmes de télécommunications
Optimisation non différentiable
Prise de décision -- Modèles mathématiques
Résumé / Abstract : Un des problèmes majeurs dans le domaine des télécommunications est de construire des réseaux robustes qui puissent faire face à l’incertitude de la demande. Ayant l’architecture d’un réseau et un budget donné pour le problème d’allocation de la capacité, le but est d’identifier une capacité faisable, qui minimise le pire cas de demande insatisfaite. Premièrement, nous formulons l’incertitude de la demande comme un polytope engendré par un nombre fini de scénarios de la demande. Nous montrons que le problème peut se ramener à la minimisation d’une fonction convexe sur un polyèdre. Nous calculons alors une solution optimale par trois méthodes de plans sécants : Kelley, Elzinga & Moore et faisceaux induits. Ensuite, nous formulons l’incertitude comme un polyèdre décrit par un nombre fini d’inégalités linéaires, ce qui résulte en un problème considérablement plus difficile. Par conséquent, nous cherchons uniquement des bornes supérieures et inférieures. Quelques idées novatrices sont présentées et l’algorithme de type « Branch & Bound » de Falk & Soland est utilisé afin de calculer le maximum d’une fonction convexe additive ; de plus, nous définissons une variante de cet algorithme, adaptée à notre situation particulière. Après avoir défini la capacité d’un réseau, l’étape suivante est de calculer le routage optimal dans ce réseau. Nous minimisons la congestion en utilisant comme objectif la fonction moyenne de retard de Kleinrock. Le problème résultant est convexe mais non-linéaire et la fonction duale est la somme d’un terme polyèdral et d’un terme différentiable. Afin de résoudre ce problème, nous implémentons un algorithme hybride basé sur la relaxation lagrangienne.