Exact algorithms for budgeted prize-collecting covering subgraph problems

• DOI: 10.1016/j.cor.2022.105798
• Publication Date: 2022-03-30T01:00:01Z
• Authors: N. Morandi; R. Leus; H. Yaman
• Keywords: Feedback vertex set; Vertex connectivity

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, but the price can also be partially collected if the vertex is covered, where an unvisited vertex is covered by a visited one if the latter belongs to the former's neighbourhood. 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 tour and a tree, and for these two cases we also identify novel symmetry-breaking inequalities.<br/>Instances and computational results are available in a public repository at https://github.com/nm05119/Exact-algorithms-for-budgeted-prize-collecting-covering-subgraph-problems<br/>