Pfetsch, Marc E. ; Rinaldi, Giovanni ; Ventura, Paolo (2024)
Optimal patchings for consecutive ones matrices.
In: Mathematical Programming Computation, 2022, 14 (1)
doi: 10.26083/tuprints-00023504
Article, Secondary publication, Publisher's Version
![[img]](https://tuprints.ulb.tu-darmstadt.de/style/images/fileicons/text.png) |
Text
s12532-021-00203-z.pdf Copyright Information: CC BY 4.0 International - Creative Commons, Attribution. Download (754kB) |
| Item Type: | Article |
|---|---|
| Type of entry: | Secondary publication |
| Title: | Optimal patchings for consecutive ones matrices |
| Language: | English |
| Date: | 26 March 2024 |
| Place of Publication: | Darmstadt |
| Year of primary publication: | March 2022 |
| Place of primary publication: | Berlin ; Heidelberg |
| Publisher: | Springer |
| Journal or Publication Title: | Mathematical Programming Computation |
| Volume of the journal: | 14 |
| Issue Number: | 1 |
| DOI: | 10.26083/tuprints-00023504 |
| Corresponding Links: | |
| Origin: | Secondary publication DeepGreen |
| 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. |
| Uncontrolled Keywords: | Consecutive ones property, Tucker matrices, Polyhedral combinatorics, Branch-and-cut |
| Status: | Publisher's Version |
| URN: | urn:nbn:de:tuda-tuprints-235041 |
| Additional Information: | Mathematics Subject Classification: Primary 90C10; Secondary 90C57 • 52B12 |
| Classification DDC: | 000 Generalities, computers, information > 004 Computer science 500 Science and mathematics > 510 Mathematics |
| Divisions: | 04 Department of Mathematics > Optimization |
| Date Deposited: | 26 Mar 2024 14:21 |
| Last Modified: | 22 Apr 2024 09:36 |
| SWORD Depositor: | Deep Green |
| URI: | https://tuprints.ulb.tu-darmstadt.de/id/eprint/23504 |
| PPN: | 517266784 |
| Export: |
 |
View Item |
Drucken
Impressum