A lagrangian method for the local access network expansion problem

Growing demand makes organizations expand and improve their local access network(LAN)s. In this research, a mixed integer program is proposed for the minimum cost network expansion plan. This model considers the tradeoff between facilities’ locations, cable type and size; investment and operating costs. Then a lagrangian relaxation solution procedure is proposed. The lagrangian relaxation problem is separated into two subproblems, one is a shortest path and the other is a knapsack problem.

Keywords:

Network Design , Integer Programming , Lagrangian Relaxation , Knapsack problem