Set Covering With Almost Consecutive Ones Property
- In this paper we consider set covering problems with a coefficient matrix almost having the consecutive ones property, i.e., in many rows of the coefficient matrix, the ones appear consecutively. 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.
Verfasser*innenangaben: | Nikolaus Ruf, Anita Schöbel |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-12696 |
Schriftenreihe (Bandnummer): | Report in Wirtschaftsmathematik (WIMA Report) (91) |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Jahr der Fertigstellung: | 2003 |
Jahr der Erstveröffentlichung: | 2003 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 11.11.2003 |
GND-Schlagwort: | set covering; consecutive ones property; stop location |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |