TU Darmstadt / ULB / TUprints

Optimal patchings for consecutive ones matrices

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] Text
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

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
Actions (login required)
View Item View Item