A heuristic algorithm based on Lagrangian relaxation for the closest string problem

作者：Tanaka Shunji^*

来源：Computers & Operations Research, 2012, 39(3): 709-717.

DOI：10.1016/j.cor.2011.06.005

• Closest string problem
• Mixed-integer programming
• Lagrangian relaxation
• Tabu search

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.

• 出版日期2012-3