A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear Programming formulation, based on Tucker characterization and on some classes of facet defining inequalities introduced by Oswald and Reinelt. We propose a method based on asteroidal triple free-graphs to derive new and more general classes of facets, and we embed them in a branch-and-cut algorithm applied to random and real instances.
Citation
Technical report, Dipartimento di Matematica 'Tullio Levi-Civita', Università degli Studi di Padova