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.
Citation
Technical Report, School of Industrial & Systems Engineering, Georgia Tech, 2006.