Optimal locations of switches and interconnections for ATM LANs

Setting up an ATM LAN with such equipment as ATM switches and cables is kno wn to be of high price. The setup cost can be minimized with optimal design while providing the required bandwidths for all demand pairs to maintain t he quality of service (QoS) requirement. In this paper, we suggest a combin ed optimization problem for determining optimal locations of switches, inte rconnections, and their capacities which can be utilized in designing ATM L AN. Two integer programming (IP) formulations are provided for the optimal network design problem. Also, the well-known Lagrangean relaxation techniqu e is applied to solve the IP formulations. With the algorithms, we can also obtain time-efficiency as well as upper and lower bounds of the optimal ob jective value. To validate our design approach, various test examples are s hown. High-quality solutions for ATM LANs with average error range of about 2.2% are generated.