Pfetsch, Marc E. ; Rinaldi, Giovanni ; Ventura, Paolo (2022)
Optimal patchings for consecutive ones matrices.
In: Mathematical Programming Computation, 14 (1)
doi: 10.1007/s12532-021-00203-z
Artikel, Bibliographie
Dies ist die neueste Version dieses Eintrags.
Kurzbeschreibung (Abstract)
We study a variant of the weighted consecutive ones property problem. Here, a 0/1-matrix is given with a cost associated to each of its entries and one has to find a minimum cost set of zero entries to be turned to ones in order to make the matrix have the consecutive ones property for rows. We investigate polyhedral and combinatorial properties of the problem and we exploit them in a branch-and-cut algorithm. In particular, we devise preprocessing rules and investigate variants of "local cuts". We test the resulting algorithm on a number of instances, and we report on these computational experiments.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2022 |
| Autor(en): | Pfetsch, Marc E. ; Rinaldi, Giovanni ; Ventura, Paolo |
| Art des Eintrags: | Bibliographie |
| Titel: | Optimal patchings for consecutive ones matrices |
| Sprache: | Englisch |
| Publikationsjahr: | März 2022 |
| Ort: | Berlin ; Heidelberg |
| Verlag: | Springer |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Mathematical Programming Computation |
| Jahrgang/Volume einer Zeitschrift: | 14 |
| (Heft-)Nummer: | 1 |
| DOI: | 10.1007/s12532-021-00203-z |
| Zugehörige Links: | |
| Kurzbeschreibung (Abstract): | We study a variant of the weighted consecutive ones property problem. Here, a 0/1-matrix is given with a cost associated to each of its entries and one has to find a minimum cost set of zero entries to be turned to ones in order to make the matrix have the consecutive ones property for rows. We investigate polyhedral and combinatorial properties of the problem and we exploit them in a branch-and-cut algorithm. In particular, we devise preprocessing rules and investigate variants of "local cuts". We test the resulting algorithm on a number of instances, and we report on these computational experiments. |
| Freie Schlagworte: | Consecutive ones property, Tucker matrices, Polyhedral combinatorics, Branch-and-cut |
| Zusätzliche Informationen: | Mathematics Subject Classification: Primary 90C10; Secondary 90C57 • 52B12 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Fachbereich(e)/-gebiet(e): | 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung |
| Hinterlegungsdatum: | 28 Mär 2024 08:35 |
| Letzte Änderung: | 28 Mär 2024 08:35 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Verfügbare Versionen dieses Eintrags
-
Optimal patchings for consecutive ones matrices. (deposited 26 Mär 2024 14:21)
- Optimal patchings for consecutive ones matrices. (deposited 28 Mär 2024 08:35) [Gegenwärtig angezeigt]
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum