Integer programming approaches to networks with equal-split restrictions

Abstract

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study.

First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families.

Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX.

Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.