A Math-Heuristic Algorithm for the DNA Sequencing Problem

One of the key issues in designing an algorithm in general, and a metaheuristic in particular, concerns the Brie tuning of one or more algorithmic parameters. In this paper, we present a simple mechanism aimed at automatically fine tuning a parameter of a novel hybrid algorithm. We design an algorithm that uses mathematical programming techniques in a metaheuristic fashion and we exploit ideas from the corridor method to drive the use of a standard MIP solver over different portions of the solution space. The size and the boundaries of such portions of the solution space are determined by the width of the corridor built around an incumbent solution. In turn, the corridor width is automatically fine tuned by the proposed mechanism, taking into account the evolution of the search process. The proposed algorithm is then tested on a well known problem from computational biology and results on a set of benchmark instances are provided.