The Robust Network Loading Problem with Dynamic Routing
AbstractThe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Department of Computer, Control and Management Engineering, Università degli Studi di Roma "La Sapienza" in its series DIS Technical Reports with number 2010-03.
Date of creation: Mar 2010
Date of revision:
network design; robustness; branch-and-cut;
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Laura Armiero).
If references are entirely missing, you can add them using this form.