Joint Optimization of Data Network Design and Facility Selection by Using Linear Programming

Abstract

The goal of optimal network design and facility engineering is to arrive at network topologies that minimize total network cost while selecting fucility types. allocating capacity. and routing traffic to accommodate demand and performance requirements. This research describes a data network design model based on a Mixed Integer/Linear Programming (M1LP) formulation. as do most other approaches. separate link capacity and facility selection from routing and topological design. it fully integrates these processes to capture the VCIY important couplings that exist between them. We show that our formulation leads to a natural decomposition of the optunal design problem into two subproblems solvable sequencially. We present a linki reduction algnrithm that efficiently design single or multifacility networks. This algorithm is based on a special-purpose monotonic greedy drop heuristic procedure.