A Lower Bound for the Internet Protocol Network Design Problem

The Internet Protocol (IP) Network Design problem (IPND) concerns the topological optimization of an IP telecommunication network. A set of nodes is given together with a set of traffic demands between pairs of nodes. Traffic demands are routed according to the Open Shortest Path First (OSPF) protocol with Equal commodity Multi-flow (ECM) splitting, based on a set of given routing weights. An integer number of capacitated devices can be configured between pairs of nodes to route all the traffic, thus giving the cost of the network. The IPND problem consists of determining a minimum cost network topology and capacity assignment such that all traffic demands are satisfied. In this work, we present a Mixed Integer Linear Programming (MILP) model and we investigate a Branch-and-Cut algorithm to derive a lower bound for IPND. Some preliminary computational results and hints for further research are also presented.