期刊
COMPUTERS & OPERATIONS RESEARCH
卷 144, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2022.105798
关键词
Prize-collecting problems; Budget; Covering problems; Branch-and-cut; Benders decomposition; Symmetry breaking
We introduce a class of budgeted prize-collecting covering subgraph problems and develop a branch-and-cut framework and a Benders decomposition for their exact solution. We observe that the former algorithm generally has shorter computational times, but the latter can outperform the former in specific instances. Additionally, we validate our algorithmic frameworks for the cases where the subgraph is a cycle and a tree, and identify novel symmetry-breaking inequalities.
We introduce a class of budgeted prize-collecting covering subgraph problems. For an input graph with prizes on the vertices and costs on the edges, the aim of these problems is to find a connected subgraph such that the cost of its edges does not exceed a given budget and its collected prize is maximum. A vertex prize is collected when the vertex is visited. Moreover, a prize is also collected if the vertex is covered, where an unvisited vertex is covered by a visited one if the latter belongs to the former's covering set. A capacity limit is imposed on the number of vertices that can be covered by the same visited vertex. Potential application areas include network design and intermodal transportation. We develop a branch-and-cut framework and a Benders decomposition for the exact solution of the problems in this class. We observe that the former algorithm results in shorter computational times on average, but also that the latter can outperform the former for specific instance settings. Finally, we validate our algorithmic frameworks for the cases where the subgraph is a cycle and a tree, and for these two cases we also identify novel symmetry-breaking inequalities.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据