The Robust Network Loading Problem with Dynamic Routing

Abstract

The Robust Network Loading Problem (RNL) can be stated as follows. Given a graph and a set of traffic matrices, install minimum cost integer capacities on the edges such that all the matrices can be routed non simultaneously on the network. The routing scheme is said to be dynamic if we can choose a (possibly) different routing for every matrix, it is called static if the routing must be the same for all the matrices. The flows are unsplittable if each point-to-point demand (commodity) must use a single path, they are splittable if the flow for every commodity can be splitted along several paths. In this paper we present the first exact approach for solving the RNL problem with splittable flows and dynamic routing under polyhedral uncertainty for the demands. A branch-and-cut algorithm based on the capacity formulation of the problem defined by metric inequalities is developed, and polyhedral results are given. The separation problem is formulated as a bilevel programming problem and a corresponding single level problem is derived. Computational results are presented.