首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Optimal patchings for consecutive ones matrices
  • 本地全文:下载
  • 作者:Marc E. Pfetsch ; Giovanni Rinaldi ; Paolo Ventura
  • 期刊名称:Mathematical Programming Computation
  • 印刷版ISSN:1867-2957
  • 出版年度:2021
  • 卷号:14
  • 期号:1
  • 页码:43-84
  • DOI:10.1007/s12532-021-00203-z
  • 语种:English
  • 出版社:Mathematical Programming Computation
  • 摘要:AbstractWe 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.
  • 关键词:Consecutive ones property;Tucker matrices;Polyhedral combinatorics;Branch-and-cut
国家哲学社会科学文献中心版权所有