Heuristic algorithm for an internet mesh network design problem

This study presents the algorithm based on Local Search heuristic used to solve the internet mesh network design problem. The network in this study is a mesh network, formulated as a Mixed Integer Programming (MIP) model. The mathematical model is tested with a branch and cut algorithm using CPLEX concert technology with C++. The proposed Local Search algorithm consists of 3 stages where each consecutive stage aims for progressive enhancement over the previous one. First, LS1 is the basic iterated Local Search algorithm. This stage introduces many insights on the solution generation and evaluation process of the algorithm. Then, LS2 aims for improvement over LS1, which utilizes the Harmony Search algorithm concept and idea. At last stage, LS3 derives an implementation from the objective function to instruct the solution generation process more efficiently. By analysis and comparison though many tested instances and scenarios, the results obtained show that LS3 yields the best performance from out of the 3 Local Search algorithm and can solve a large problem size that a branch and cut algorithm cannot manage.