Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Valid inequalities for a shortest-path routing optimization problem

  • Artur Tomaszewski
  • Michal Pioro
  • Mateusz Dzida
  • Mariusz Mycek
  • Michal Zagozdzon
Publiceringsår: 2007
Språk: Engelska
Dokumenttyp: Konferensbidrag


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.


  • Electrical Engineering, Electronic Engineering, Information Engineering
  • IP networks
  • OSPF routing optimization
  • ECMP flow
  • Branch-and-cut


International Network Optimization Conference INOC 2007

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen