Optimization Online


An integer programming approach to the OSPF weight setting problem

Amandeep Parmar (aparmar***at***isye.gatech.edu)
Shabbir Ahmed (sahmed***at***gatech.edu)
Joel Sokol (jsokol***at***isye.gatech.edu)

Abstract: Under the Open Shortest Path First (OSPF) protocol, traffic flow in an Internet Protocol (IP) network is routed on the shortest paths between each source and destination. The shortest path is calculated based on pre-assigned weights on the network links. The OSPF weight setting problem is to determine a set of weights such that, if the flow is routed based on the OSPF protocol, some measure of network congestion is minimized. A variety of optimization approaches for this strongly $NP$-hard problem have been proposed. However, the existing studies develop heuristic solution methods without any quality guarantees. In this paper we propose an integer programming based solution strategy for the OSPF weight setting problem so as to obtain solutions with quality guarantees. We develop a family of valid inequalities for a mixed-integer linear programming formulation of the problem. These inequalities are incorporated within a branch-and-cut algorithm. Computational experiments using some randomly generated test problems and some problems taken from the literature indicate that the proposed approach is able to provide feasible solutions with significantly smaller optimality gaps than those provided by the state-of-the-art integer programming solver CPLEX.

Keywords: OSPF routing, Integer Programming, Cutting Planes

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Network Optimization

Citation: Technical Report, School of Industrial & Systems Engineering, Georgia Tech, 2006.

Download: [PDF]

Entry Submitted: 10/24/2006
Entry Accepted: 10/24/2006
Entry Last Modified: 10/24/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society