IDEAS home Printed from
   My bibliography  Save this paper

The Robust Network Loading Problem with Dynamic Routing


  • Sara Mattia

    () (Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma)


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.

Suggested Citation

  • Sara Mattia, 2010. "The Robust Network Loading Problem with Dynamic Routing," DIS Technical Reports 2010-03, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
  • Handle: RePEc:aeg:wpaper:2010-3

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Sylvie Borne & Eric Gourdin & Bernard Liau & A. Mahjoub, 2006. "Design of survivable IP-over-optical networks," Annals of Operations Research, Springer, vol. 146(1), pages 41-73, September.
    2. Luís Gouveia & Pedro Patrício & Amaro Sousa, 2008. "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM," Networks and Spatial Economics, Springer, vol. 8(1), pages 3-21, March.
    3. Knippel, Arnaud & Lardeux, Benoit, 2007. "The multi-layered network design problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 87-99, November.
    4. Arie M. C. A. Koster & Adrian Zymolka, 2007. "Tight LP-based lower bounds for wavelength conversion in optical networks," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 115-136.
    Full references (including those not matched with items on IDEAS)

    More about this item


    network design; robustness; branch-and-cut;


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:aeg:wpaper:2010-3. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Antonietta Angelica Zucconi). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.