Improved optimization modelling for the closest string and related problems

We present a new integer linear programming model for the closest string problem. This model requires considerably less variables and constraints than the popular binary linear programming model used for this purpose. Due to the reduced size it is easier to handle rounding errors when an LP relaxation technique is used to solve the problem.The proposed model is particularly useful for closest string problems where a small set of long sequences is given. In this case, the optimal string or a good approximate solution can be usually obtained by rounding the optimal solution of the LP relaxation to the nearest integers.