Advanced

Valid inequalities for a shortest-path routing optimization problem

Tomaszewski, Artur; Pioro, Michal LU ; Dzida, Mateusz; Mycek, Mariusz and Zagozdzon, Michal (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:
author
organization
publishing date
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
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
2008-02-05 13:44:34
date last changed
2016-04-16 10:43:34
@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},
  keyword      = {IP networks,OSPF routing optimization,ECMP flow,Branch-and-cut},
  language     = {eng},
  pages        = {10},
  title        = {Valid inequalities for a shortest-path routing optimization problem},
  year         = {2007},
}