An ATM Switch Capacity Allocation Problem

In this paper, we consider a capacity allocation problem arising in the context of deploying asynchronous transfer mode (ATM) networks. Given types of ATM switches, the problem is to find an optimal allocation of capacity such that the total cost of installed switch modules is minimized, while satisfying all traffic demands. We formulate the problem as an integer programming model, which can be conceptualized as a generalized bin packing problem with capacity constraints. We then develop a surrogate constraint technique of the formulation for enhancing the representation of the model. Guided by the tight lower bound of the surrogate relaxation, we devise an effective tabu search heuristic that provides good quality solutions with guaranteed optimality. We present promising computational results that show the viability of the proposed heuristic and lower bounding methods, and that provide insights into implementation for configuring ATM switch in practice.     

A Location-Routing Problem in Designing Optical Internet Access with WDM Systems

In this paper, we deal with a location-routing problem in designing the optical Internet with WDM systems. This problem arises from the design of broadband local access networks that deliver high-speed access service to residential subscribers. The problem is to find an optimal location of the gateway and optimal routing of traffic demands in the optical access network. We develop mixed-integer programming models for solving the location-routing problem to minimize the total cost of network elements used in the network while carrying the offered traffic. By exploiting the inherent structure of the problem, we derive two effective tabu search procedures. We present promising computational results of the proposed solution procedures.     

A Fiber Routing Problem in Designing Optical Transport Networks with Wavelength Division Multiplexed Systems

In this paper, we consider a fiber routing problem arising from the design of optical transport networks. The problem is to find an optimal routing of multiple rings and an optimal location of wavelength division multiplexed (WDM) systems for carrying demand traffic. This problem can be conceptualized as a Steiner (multiple) ring problem with link capacity constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut procedure along with preprocessing routines and valid inequalities for optimally solving the problem. Exploiting the inherent special structures of the formulation, we focus on developing strong valid inequalities and devising an effective Tabu search heuristic for solving large-scale problems. Computational results indicate that preprocessing rules and valid inequalities provide a tight lower bound, and in turn reduce the effort required to solve the problem within the framework of the branch-and-cut procedure. Moreover, the proposed Tabu search heuristic works quite well for solving large-scale problems. Motivated by promising computational results, we provide insights into implementing the proposed branch-and-cut procedure for deploying fiber optic networks in practice.