| This paper considers the following NP-hard network topology design (NTD) problem called NTD-CB/R: given (i) the location of network nodes, (ii) connecting links, and (iii) each link’s reliability, cost and bandwidth, design a topology with minimum cost (C) and maximum bandwidth (B) subject to a pre-defined reliability (R) constraint. A key challenge when solving the bi-objective optimization problem is to simultaneously minimize C while maximizing B. Existing solution aims to obtain one topology with the largest bandwidth cost ratio (bcr). To this end, this paper aims to generate the best set of non-dominated feasible topologies, aka the Pareto Optimal Set (POS). It formally defines a dynamic programming (DP) formulation for NTD-CB/R. Then, it proposes two alternative Lagrange Relaxations to compute a weight for each link from its reliability, bandwidth, and cost. The paper further proposes a DP approach, called DPCB/R-LP, to generate POS with maximum weight. It also describes a heuristic to enumerate only k ? n paths to reduce computational complexity for a network with n possible paths. Extensive simulations on hundreds of various sized networks that contain up to 299 paths show that DPCB/R-LP can generate 70.4% of optimal POS while using only up to 984 paths and 27.06 CPU seconds. With respect to a widely used metric, called overall-pareto-spread (OS), DPCB/R-LP produces 94.4% of POS with the best OS. Finally, each generated POS contains a topology that has the largest bcr, significantly improving the existing method. |