Set covering with almost consecutive ones property

Abstract

In this paper, we consider set covering problems with a coefficient matrix almost having the consecutive ones property, i.e., in most rows of the coefficient matrix, the ones appear consecutively and only a few blocks of consecutive ones appear in the remaining rows. If this property holds for all rows it is well known that the set covering problem can be solved efficiently. For our case of almost consecutive ones we present a reformulation exploiting the consecutive ones structure to develop bounds and a branching scheme. Our approach has been tested on real-world data as well as on theoretical problem instances.