A heuristic algorithm based on Lagrangian relaxation for the closest string problem |
| |
Authors: | Shunji Tanaka |
| |
Affiliation: | Department of Electrical Engineering, Kyoto University, Kyotodaigaku-Katsura, Nishikyo-ku, Kyoto 615-8510, Japan |
| |
Abstract: | The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast. |
| |
Keywords: | Closest string problem Mixed-integer programming Lagrangian relaxation Tabu search |
本文献已被 ScienceDirect 等数据库收录! |
|