Invited Session Fri.3.H 3503

Friday, 15:15 - 16:45 h, Room: H 3503

Cluster 23: Telecommunications & networks [...]

Robust network design and applications


Chair: Christian Raack



Friday, 15:15 - 15:40 h, Room: H 3503, Talk 1

Agostinho Agra
The robust vehicle routing problem with time windows

Coauthors: Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss, Cristina Requejo


This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on maritime transportation instances.



Friday, 15:45 - 16:10 h, Room: H 3503, Talk 2

Sara Mattia
The robust network loading problem


The Robust Network Loading (RNL) problem is a generalization of the well known Network Loading (NL) problem. Given a graph with capacity installation costs for the edges, the RNL problem consists of choosing minimum cost integer capacities to serve all the demands belonging to a given polyhedron of feasible traffic matrices. If the routing scheme must be the same for all the matrices, it is called static or oblivious; if it can be changed according to the matrix, it is called dynamic. If each point-to-point demand in the matrix must be routed using a single path, the flows are called unsplittable, otherwise they are said to be splittable. In this talk we present an algorithm for solving the RNL with dynamic routing and splittable flows and a preliminary comparison between the static and the dynamic approach.



Friday, 16:15 - 16:40 h, Room: H 3503, Talk 3

Fabio D'Andreagiovanni
On the adoption of multi-band uncertainty in robust network design

Coauthor: Christina Büsing


Handling uncertainty in the design of telecommunication networks has become a key challenge for leading network operators. Uncertainty in Network Design has been mainly tackled by the Bertsimas-Sim model (BS). However, the central assumption of BS that the deviation band of each uncertain parameter is single may be too limitative in practice: experience indeed suggests that relevant deviations also occur internally and asymmetrically over the band. Breaking the band into multiple sub-bands looks thus advisable.
In this work, we study the robust counterpart of an LP with uncertain coefficient matrix, when a multi-band uncertainty set is considered. We show that the robust counterpart corresponds to a compact LP formulation and that separating robustness cuts corresponds to solving a min-cost flow problem. Finally, we assess the effectiveness of our approach on realistic instances of robust network design problems considered by our industrial partners.

  1. D. Bertsimas, M. Sim, The Price of Robustness, Oper. Res. 52 (1), 35-53, 2004

  2. C. Büsing, F. D'Andreagiovanni, New results about multi-band uncertainty in Robust Optimization, to appear in Proc. of SEA2012


  quick loans . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.