Simulated annealing applied to the MWPT problem

Abstract

The Minimum Weight Pseudo-Triangulation (MWPT) problem is suspected to be NP-hard. We show here how Simulated Annealing (SA) can be applied for obtaining approximate solutions to the optimal ones. To do that, we applied two SA algorithms, the basic version and our extended hybrid version of SA. Through the experimental evaluation and statistical study we assess the applicability and performance of the SA algorithms. The obtained results show the benefits of using the hybrid version of SA to achieve improved and higher quality solutions for the MWPT problem.