Sorting permutations by reversals through branch-and-price

We describe an exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in m olecular biology. Our approach is based on an integer linear programming fo rmulation of a graph-theoretic relaxation of the problem, calling for a dec omposition of the edge set of a bicolored graph into the maximum number of alternating cycles. The formulation has one variable for each alternating c ycle, and the associated linear programming relaxation is solved by column generation. A major advantage with respect to previous approaches is that the subproble m to face in the column-generation phase no longer requires the solution of min-cost general matching problems, but of min-cost bipartite matching pro blems. Experiments show that there is a tremendous speed-up in going from g eneral matching to bipartite matching, although the best-known algorithms f or the two problems have the same theoretical worst-case complexity. We als o show the worst-case ratio between the lower bound value obtained by our n ew method and previous ones. We illustrate the effectiveness of our approach through extensive computati onal experiments. In particular, we can solve to proven optimality the larg est real-world instances from the literature in a few seconds, and the othe r (smaller) real-world instances within a few milliseconds on a workstation . Moreover, we can solve to optimality random instances with n = 100 within 3 seconds, and with n = 200 within 15 minutes, where n is the size of the permutation, whereas the size of the instances solvable by previous approac hes was at most 100. We also describe a polynomial-time heuristic algorithm that consistently finds solutions within 2% of the optimum for random inst ances with n up to 1000.