Groupe d’études et de recherche en analyse des décisions


A practicable robust counterpart formulation for decomposable functions: A network congestion case study

, et

Robust optimization (RO) is a powerful mean to handle optimization problems where there is a set of parameters that are uncertain. The effectiveness of the method is especially noticeable when these parameters are only known to lie inside some uncertainty region. Unfortunately, there are important computational considerations that have prevented the methodology from being fully adopted in fields of practice where the cost function that needs to be robustified is nonlinear with respect to such parameters. In this paper, we propose a new robust optimization formulation that circumvent the computational burden in problems where the cost decomposes as the sum of convex costs for each decision variable. This is done by exploiting the fact that in this formulation the worst-case cost function can be expressed as a convex combination between a nominal and an upper-bound cost function. One can still control the conservatism of the robust solution by adjusting how many terms of the total cost function can simultaneously reach their respective most pessimistic value. In order to demonstrate the potential of our "practicable robust counterpart" formulation, we present how it can be employed on the robust optimization of packet routing on a telecommunication network with congestion. In such problems, an important source of uncertainty stems from the queueing delay, which is perhaps best approximated by a nonlinear convex function using the theory of M/M/1 queueing systems. Computational results on a large number of problem instances of realistic size confirm that it is possible to identify robust solutions that significantly outperform a deterministic approach in terms of both the amount of congestion and the risks of excess congestion. Moreover, our proposed method also improves significantly the quality of solutions that are obtained compared to an approximation scheme that is naively based on linearizing the delay function.

, 38 pages