摘要：The Minimum Latency Problem (MLP) is a class of combinational optimization problems that has many practical applications. In the general case, the MLP is proved to be NP-hard. One of the approaches to solve the problem is using exact algorithms. However, the algorithms which were recently proposed are applied only to the problems with small size, i.e., 26 vertices. In this paper, we present a new exact algorithm to solve the MLPs with a larger size. Our algorithm is based on the branch and bound method and it has two new rules that improve the pruning technique. We have evaluated the algorithm on several data sets. The results show that the problems up to 40 vertices can be solved exactly.
关键词：Minimum Latency Problem (MLP); exact algorithm; branch and bound method
Loading...
