Consecutive Ones and A Betweenness Problem in Computational Biology

. In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integer programming formulation of the problem and makes use of automatically generated facet-defining inequalities. 1 Introduction The general Betweenness Problem is the following combinatorial optimization problem. We are given a set of n objects 1; 2; : : : ; n, a set B of betweenness conditions, and a set B of non-betweenness conditions. Every element of B (of B) is a triple (i; j; k) (a triple (i; j; k)) requesting that object j should be placed (should not be placed) between objects i and k. The task is to find a linear order of all objects such that as many betweenness and non-betweenness conditions are satisfied, resp. to characterize all or..