Division of Optimization and Systems Theory
Department of Mathematics
A brief review of telecommunications networks design and a discussion of optimization models and solution strategies is given. Next the specific problems studied in the four appended papers of the thesis are described including proposed solution schemes and computional results. The solution strategies include Lagrangian decomposition and Lagrangian relaxation, specialized branch-and-bound strategies, and LP-based branch-and-cut together with valid inequalities. The decomposition methods induce subproblems that are Steiner tree problems, binary and continuous knapsack problems, and shortest path problems.
The four specific network design problems considered are: general step cost capacity dimensioning of a multicast enabled backbone communications network, capacity dimensioning of a multicast network with shortest path tree restrictions on achievable routing distribution tree topologies, Rendezvous Point (RP) placement problem for shared multicast trees in an existing shortest path routing network, and finally, unicast network capacity dimensioning problem with general step costs and single path routing.