Valid inequalities for a shortest-path routing optimization problem
(2007) International Network Optimization Conference INOC 2007- Abstract
- In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example
according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized
on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem
can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective
cuts (valid inequalities) can be derived. In this paper we present exact and approximate LP- and MIPbased
methods for generating valid inequalities that separate fractional solutions of the basic problem.
Besides, a family of complementary valid inequalities, generated with... (More) - In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example
according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized
on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem
can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective
cuts (valid inequalities) can be derived. In this paper we present exact and approximate LP- and MIPbased
methods for generating valid inequalities that separate fractional solutions of the basic problem.
Besides, a family of complementary valid inequalities, generated with a shortest-path algorithm, related
to combinatorial properties of feasible traffic routes is introduced to speed up the cut generation process.
Results of a numerical study illustrating computational issues are discussed. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1024460
- author
- Tomaszewski, Artur ; Pioro, Michal LU ; Dzida, Mateusz ; Mycek, Mariusz and Zagozdzon, Michal
- organization
- publishing date
- 2007
- type
- Contribution to conference
- publication status
- published
- subject
- keywords
- IP networks, OSPF routing optimization, ECMP flow, Branch-and-cut
- pages
- 10 pages
- conference name
- International Network Optimization Conference INOC 2007
- conference location
- Spa, Belgium
- conference dates
- 2007-04-22 - 2007-04-25
- language
- English
- LU publication?
- yes
- id
- 5ecf566e-9e21-4151-99e0-72ccde24fa96 (old id 1024460)
- alternative location
- http://www.poms.ucl.ac.be/inoc2007/Papers/author.95/paper/paper.95.pdf
- date added to LUP
- 2016-04-04 12:59:54
- date last changed
- 2018-11-21 21:11:43
@misc{5ecf566e-9e21-4151-99e0-72ccde24fa96,
abstract = {{In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example<br/><br>
according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized<br/><br>
on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem<br/><br>
can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective<br/><br>
cuts (valid inequalities) can be derived. In this paper we present exact and approximate LP- and MIPbased<br/><br>
methods for generating valid inequalities that separate fractional solutions of the basic problem.<br/><br>
Besides, a family of complementary valid inequalities, generated with a shortest-path algorithm, related<br/><br>
to combinatorial properties of feasible traffic routes is introduced to speed up the cut generation process.<br/><br>
Results of a numerical study illustrating computational issues are discussed.}},
author = {{Tomaszewski, Artur and Pioro, Michal and Dzida, Mateusz and Mycek, Mariusz and Zagozdzon, Michal}},
keywords = {{IP networks; OSPF routing optimization; ECMP flow; Branch-and-cut}},
language = {{eng}},
title = {{Valid inequalities for a shortest-path routing optimization problem}},
url = {{http://www.poms.ucl.ac.be/inoc2007/Papers/author.95/paper/paper.95.pdf}},
year = {{2007}},
}