Title: On generating Pareto optimal set in bi-objective reliable network topology design

Authors: Basima Elshqeirat; Ahmad Aloqaily; Sieteng Soh; Kwan-Wu Chin; Amitava Datta

Addresses: King Abdullah II School of Information Technology, The University of Jordan, Amman, Jordan ' Department of Computer Science and its Applications, Prince Hussein Bin Abdullah II for Information Technology, The Hashemite University, Zarqa, Jordan ' Department of Computing, Curtin University, Bentley, Perth, Western Australia, Australia ' Faculty of Engineering and Information Sciences, University of Wollongong, Wollongong, New South Wales, Australia ' Department Computer Science and Software Engineering, University of Western Australia, Perth, New South Wales, Australia

Abstract: This paper considers an NP-hard network topology design (NTD) problem called NTD-CB/R. A key challenge when solving the bi-objective optimisation problem is to simultaneously minimise cost while maximising bandwidth. This paper aims to generate the best set of non-dominated feasible topologies, known as 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. The paper proposes a DP approach, called DPCB/R-LP, to generate POS with maximum weight. Extensive simulations on hundreds of networks that contain up to 299 paths show that DPCB/R-LP can generate 70.4% of the optimal POS while using only up to 984 paths and 27.06 CPU seconds. Overall-Pareto-spread (OR), DPCB/R-LP produces 94.4% of POS with OS = 1, measured against the optimal POS. Finally, all generated POS's with largest bcr, significantly higher than 88% obtained by existing methods.

Keywords: bi-objective optimisation; dynamic programming; Lagrange relaxation; Pareto optimal set; network reliability; topology design.

DOI: 10.1504/IJGUC.2023.132616

International Journal of Grid and Utility Computing, 2023 Vol.14 No.4, pp.339 - 355

Received: 22 Feb 2020
Accepted: 17 May 2020
Published online: 31 Jul 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article