.png){kind=icon}
返回
A branch-and-cut algorithm for the maximum covering cycle problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-018-2856-5.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In many applications, such as telecommunications and routing, we seek for cost-effective infrastructure or operating layouts so that many nodes (e.g., customers) of a support network (typically modeled by a graph) are covered by, or at least are easily reachable from, such a layout. In this paper, we study the maximum covering cycle problem. In this problem we are given a non-complete graph, and the goal is to find a cycle, such that the number of nodes which are either on the cycle or are adjacent to the cycle is maximized. We design a branch-and-cut framework for solving the problem. The framework contains valid inequalities, lifted inequalities and a primal heuristic. In a computational study, we compare our framework to previous work available for this problem. The results reveal that our approach significantly outperforms the previous approach. In particular, all available instances from the literature could be solved to optimality with our approach, most of them within a few seconds.
Keyword:
Covering problems
Branch-and-cut
Optimal cycle problems
Domination problems
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.5
论文数:
8.1K
被引数:
2.1W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容