.png){kind=icon}
.png){kind=icon}
Return
A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2023.106151.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given an undirected graph.. with a cost function on vertices, a collection of subgraphs of G such that in each subgraph, there are some distinguished vertices called terminals, the Partitioned Steiner Tree Problem (PSTP) asks for a minimum cost vertex set such that, in each of the given subgraph G(i), the graph induced by the vertex set spans the terminal set in G(i). The PSTP generalizes the well-known Steiner tree problem and has important applications in computational sustainability, network design, and social network analysis. However, for solving the PSTP, conventional integer programming approaches based on single-commodity flow, multi-commodity flow and subtour elimination integer linear programs, suffer from low computational efficiency due to a substantial number of variables. In this paper, we propose a compact vertex-separator-based integer linear programming formulation with much fewer variables. Enhancing inequalities are also studied for tightening the formulation. We further investigate a branch-and-cut algorithm, a local-branching heuristic algorithm, and a hybrid algorithm combining them. In experiments where both public real-world and synthetic graphs are used, our hybrid algorithm outperforms all conventional approaches, especially for large graphs with more than ten thousand vertices. Further tests also validate the effectiveness of the proposed formulation and enhancing inequalities.
Keywords:
Partitioned Steiner tree problem
Integer linear program
Vertex-separator
Branch-and-cut
Local branching
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
