Rechercher

[BEG15] Flot maximum robuste avec incertitudes sur les chemins

Conférence Nationale avec comité de lecture : 16ème congrès annuel de la ROADEF, February 2015, pp.1, Marseille, France,

Auteurs: C. Bentz , S. Elloumi , E. Gourdin , T. Lefebvre

Mots clés: Flot maximum, incertitudes, optimisation robuste.

Résumé: Depuis les premiers travaux de Ford et Fulkerson [8] sur le sujet, le problème de flot maximum a été l’objet d’importantes études, et de nombreux algorithmes permettant de le résoudre ont été proposés dans la littérature [1]. Ce problème trouve de nombreuses applica- tions, notamment dans le domaine des télécommunications. Dans ce contexte, il est fréquent que des événements imprévus entravent l’acheminement d’informations au sein du réseau. On pense en particulier à des pannes de matériel ou à une réduction du débit due à des phénomènes de congestion. Un bon moyen de se prémunir contre les effets de tels événements consiste à les prendre explicitement en compte lors de l’élaboration du routage. Cette approche permet d’envoyer un flux de données de la source vers le terminal même si on ne dispose que d’in- formations parcellaires sur l’état du réseau. L’optimisation robuste est un outil naturellement adapté à la formulation puis à la résolution de problèmes de routage dans les réseaux en pré- sence d’incertitudes [2, 4, 5, 6, 9, 10, 11]. Notre approche part de la formulation du problème de flot maximum vu comme un problème de «packing» fractionnaire de chemins simples entre la source et le terminal, dans un graphe où chaque lien est muni d’une capacité. Connaissant, pour chaque lien, sa probabilité empirique d’être disponible, nous pouvons associer à chaque chemin une probabilité de pouvoir acheminer du flot. Plus précisément, nous supposons que nous avons à disposition un ensemble de taille polynomial de chemins, avec pour chacun d’entre eux sa probabilité empirique de pouvoir acheminer des données de la source jusqu’au terminal. À par- tir de ces probabilités, nous définissons un ensemble d’incertitude, basé sur une idée proposée par Bandi et Bertsimas [3] que nous adaptons pour prendre en compte la non indépendance, au sens probabiliste, dans la disponibilité des chemins. Notre ensemble d’incertitude est similaire à ceux proposés par Bertsimas et Sim [7] pour un choix judicieux de paramètre. Nous obtenons alors un problème d’optimisation robuste où l’incertitude porte sur la disponibilité des chemins considérés. Notre problème de flot maximum robuste consiste à affecter une quantité de flot à chaque chemin, tout en respectant les contraintes de capacités, de sorte que la quantité de flot reçue par le terminal lors de l’occurrence du pire scénario de l’ensemble d’incertitude soit la plus grande possible. Nous montrons que ce problème peut s’écrire comme un max-min que nous résolvons en nous appuyant sur le dual du problème de minimisation et sur certaines propriétés de la matrice des contraintes. La structure particulière du problème nous assure que ce dernier admet toujours au moins une solution qu’il est possible de trouver en temps polynomial. Enfin, nous effectuons des expérimentations sur des réseaux réalistes. Références: [1] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows : theory, algorithms, and applications. [2] Babonneau, F., Klopfenstein, O., Ouorou, A., and Vial, J. P. (2009). Robust capacity expansion solutions for telecommunication networks with uncertain demands. Technical paper, Orange Labs R&D. [3] Bandi, C., and Bertsimas, D. (2012). Tractable stochastic analysis in high dimensions via robust optimization. Mathematical programming, 134(1), 23-70. [4] Ben-Ameur, W., and Zotkiewicz, M. (2011). Robust routing and optimal partitioning of a traffic demand polytope. International Transactions in Operational Research, 18(3), 307- 333. [5] Bertsimas, D., Nasrabadi, E., and Stiller, S. (2013). Robust and adaptive network flows. Operations Research, 61(5), 1218-1242. [6] Bertsimas, D., and Sim, M. (2003). Robust discrete optimization and network flows. Ma- thematical programming, 98(1-3), 49-71. [7] Bertsimas, D., and Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53. [8] Ford, L. R., and Fulkerson, D. R. (1956). Maximal flow through a network. Canadian journal of Mathematics, 8(3), 399-404. [9] Hervet, C., Faye, A., Costa, M. C., Chardy, M., and Francfort, S. (2013). Solving the Two- Stage Robust FTTH network design Problem under Demand Uncertainty. Electronic Notes in Discrete Mathematics, 41, 335-342. [10] Minoux, M. (2009). On robust maximum flow with polyhedral uncertainty sets. Optimi- zation Letters, 3(3), 367-376. [11] Petrou, G., Lemaréchal, C., and Ouorou, A. (2007). An approach to robust network design in telecommunications. RAIRO-Operations Research, 41(04), 411-426.

Equipe: oc
Collaboration:

BibTeX

@inproceedings {
BEG15,
title="{Flot maximum robuste avec incertitudes sur les chemins}",
author=" C. Bentz and S. Elloumi and E. Gourdin and T. Lefebvre ",
booktitle="{ 16ème congrès annuel de la ROADEF}",
year=2015,
month="February",
pages="1",
address="Marseille, France",
}