Multiobjective network topology design

Multiobjective network design is known to be a notoriously hard problem. Unfortunately, the problem has several practical applications such as multicast communication and VLSI design. Most network topology design problems involve simultaneously optimizing multiple conflicting objectives such as average delay and network equipment cost while satisfying flow and reliability constraints. In this paper, we formalize a network design problem and present randomized and deterministic heuristics to solve the problem. We first present a multi-objective evolutionary algorithm which obtains a diverse set of near-optimal solutions. We also design a multiobjective deterministic heuristic based on branch exchange. We test our algorithms on Poisson and Self-similar traffic models using data collected from real networks. We empirically show that our heuristics perform well across networks of various sizes.