MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTERobust Metric Inequalities for the Gamma-Robust Network Loading Problem
par Issam Tahiri
| Date : | 05/12/12 | | Time : | 10:30 | | Location : | Galois Coriolis |
Ă‚' The network loading problem aims at determining the necessary (integer) edge capacity resources of a network such that all commodities can be routed while the total installation cost is minimized. This problem occurs in many applications such as telecommunications, logistics, etc. Since the traffic requirements are in general non-deterministic, the consideration of a single traffic matrix is too restrictive. Instead of a dynamic routing approach that considers several traffic matrices in a two stage concept, we apply the Gamma-robustness approach with static routing incorporating demand uncertainties. This leads to a robust one stage model being easier to handle in practice, e.g., by avoiding updating times necessary to implement rerouting decisions. Furthermore, we generalize the class of metric inequalities to the robust setting and show that they describe the robust network loading polytope completely in the capacity space, where the classical metric inequalities are not sufficient. We describe a polynomial time exact algorithm to separate violated robust metric inequalities as model constraints. Moreover, an exact separation algorithm is presented which is used in a Cut and Branch approach. Finally, computational results using real-life telecommunication data state the performance of robust metric inequalities and the potential for large networks.
Page des séminaires
| 
