A Nested Benders Decomposition Approach for Telecommunication Network Planning

Despite its ability to result in more effective network plans, the telecommunication network planning problem with signal-to-interference ratio constraints gained less attention than the power-based one because of its complexity. In this article, we provide an exact solution method for this class of problems that combines combinatorial Benders decomposition, classical Benders decomposition, and valid cuts in a nested way. Combinatorial Benders decomposition is first applied, leading to a binary master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition. The algorithm is enhanced using valid cuts that are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem. The valid cuts proved efficient in reducing the number of times the combinatorial Benders master problem is solved and in reducing the overall computational time. More than 120 instances of the W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality. (C) 2010 Wiley Periodicals. Inc. Naval Research Logistics 57: 519-539, 2010