A Lagrangian Heuristic for Missile Defense Location Problems

This paper proposes a different solution method for solving the Missile Defence Location Problem described by Bloemen et al. [1]. They applied two solution approaches to this problem: simulated annealing (a heuristic method) and an exact solution method. Simulated annealing produces results within a short amount of computation time, however simulated annealing does not say how good its results are. The exact solution method uses an integer programming formulation which can be solved to optimality using a standard solver. The downside of this approach is that the computation time is significantly higher. Due to the exact method, it was shown that the results of simulated annealing were actually quite good. Combining time efficiency and having a confidence level for the solution, we approach the problem this time via a heuristic algorithm based upon Lagrangian relaxation and subgradient optimization. Such an algorithm is described by Beasley [2]. In section 2 we explain the Missile Defence Location Problem. Before presenting our Lagrangian heuristic in section 4, we will show the original model and also explain the used notation in section 3. In section 5 we give a summary about the data used in the model. The results obtained by our heuristic are analysed in section 6. Finally some conclusions are drawn in section 7.