A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem

• Published in: Computers & operations research 2023-05, Vol.153, p.106151, Article 106151
• Main Authors: Ma, Mengfan, Men, Ziyang, Rossi, André, Zhou, Yi, Xiao, Mingyu
• Format: Article
• Language: English
• Subjects: Branch-and-cut; Computer Science; Integer linear program; Local branching; Partitioned Steiner tree problem; Vertex-separator
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2023.106151

Given an undirected graph G 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 Gi, the graph induced by the vertex set spans the terminal set in Gi. 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. •We propose a vertex-separator-based ILP formulations for the Partitioned Steiner Tree Problem•New enhancing inequalities are introduced to tighten the formulation•A branch-and-cut, a local-branching heuristic and a hybrid algorithm are proposed•We carry out comparison experiments on five benchmark graph sets•The results show our algorithms outperform all ILP formulations of the literature