A unified integer programming model for genome rearrangement problems

We describe an integer programming (IP) model that can be applied to the solution of all genome-rearrangement problems in the literature. No direct IP model for such problems had ever been proposed prior to this work. Our model employs an exponential number of variables, but it can be solved by column generation techniques. I.e., we start with a small number of variables and we show how the correct missing variables can be added to the model in polynomial time.