A Lagrangian relaxation technique for optimizing interconnection of Local Area Networks

This paper addresses the problem of interconnecting a group of Local Area Networks (LANs) with bridges. The network designer would like to minimize the cost of connecting the LANs while maintaining acceptable traffic intensity levels on each of the LANs and the bridges. This problem belongs to the class of fixed charge network flow problems. A Lagrangian relaxation algorithm is proposed that incorporates two sets of constraints into the objective function. The relaxed problem has a special structure and can be solved as a minimum spanning tree problem and a set of shortest path problems. The subgradient algorithm is then used to maximize the Lagrangian dual. A Lagrangian heuristic algorithm is also proposed to find good primal feasible solutions. For problems with five LANs, the heuristic solutions are normally within 1% of the optimum. For larger problems the heuristic solutions are close to the lower bounds generated by Lagrangian relaxation algorithm. This suggests that the quality of the heuristic solutions does not deteriorate as the dimension of the problem grows.