Learning to Prune Instances of Steiner Tree Problem in Graphs

• $i\in N=\{1,2,..,n\}=\left\{1\right\}\cup V\cup S$: The index number of root node is 1. Here, $\left\{1\right\}\cup V$ is the set of terminal nodes and $S$ is the set of remaining nodes.

• $E=\left\{\right(i,j\left)\right\}$ : Set of directed edges. Note that the size of $E$ is double the size of the edge set of the undirected graph.

• $G=(N,E)$: A graph where the set $N$ defines the set of nodes, the set $E$ defines the set of directed edges and the set $\left\{1\right\}\cup V\subseteq N$ defines the set of terminals.

• $T\subset E$ : Set of edges that represents a tree spanning $\left\{1\right\}\cup V$ in $G$.

• $c_{ij}\in R^{+}$: The cost of the arc $(i,j)$, for all $(i,j)\in E$.

• $y_{ij}\in \{0,1\}$: This variable is equal to 1, if edge $(i,j)$ is in the set $T$. Otherwise, the decision variable is equal to zero.

• $x_{ij}^k$: This is the amount of commodity $k$ (the amount of flow from node $1$ to $k$) that goes through edge $(i,j)$.

Minimize the total cost of $T$:

As described before, we use an embedded multi-commodity network flow problem to describe the connectivity of the Steiner tree problem. In constraint 2, one unit of commodity k must be transmitted from node 1 to node k. Constraint 3 indicates that when the flow is allowed in an edge, the edge must be in the solution. Constraint 4 enforces that the flow on any edge is non-negative while Constraint 5 enforces that the variables $y_{ij}$ are binary. Constraints 2- 5 indicate that a feasible solution must have a directed path of edges (i. e. $y_{ij}=1$) between node 1 and a node belonging to $V$.

The first feature is the value of edge variables $y_{ij}$ in the LP relaxation of the problem. A high value of this variable suggests a higher likelihood of the edge appearing in the optimal solution. We didn’t consider any signals from the dual of the problem and we also didn’t utilise the variables $x_{ij}^k$ in this study. Note that the computation of LP relaxation requires significantly less time compared to the ILP computation.

We used the following weight-related features: normalised weight, standardised weight, chi-square of normalised weight and local rank of edge $(i,j)$ at node $i$ and $j$. Here, local rank refers to the rank of this edge in the sorted order of all edges (by weight) incident at the node.

To capture the discriminative power of an edge further, we also use the centrality of the incident nodes. Intuitively, the edges between highly central nodes are more likely to be part of optimal Steiner trees as they are crucial for low-weight connectivity. Specifically, we use the following centrality features: degree centrality, betweenness centrality and Eigenvector centrality. For all centrality features, NetworkX is used to construct the graph and calculate the feature values [15]. As these centrality features are focusing on nodes instead of edges, each centrality is calculated as the minimum value and the maximal value of the two incident nodes $i$ and $j$ for each edge $(i,j)$.

Degree centrality is defined as the number of links incident upon a node, which is the simplest centrality feature to calculate. It simply measures the importance of a node by how many edges are incident to it. Betweenness centrality is widely used in weighted graphs as it captures the fraction of shortest paths passing through a given node [16]. Eigenvector centrality is also an important centrality feature that captures the “influence” of a node in the network: A high eigenvector score means that a node is connected to many nodes who themselves have high scores.

The feature importance for training the model is shown in Table 1. Unsuprisingly, it shows that the LP relaxation feature is the most discriminative of all. An important observation here is that even though LP relaxation feature is important, it accounts for less than half of the discriminative power of all the features. This implies that this feature alone isn’t enough, but other features also contribute significantly to improving the accuracy of the classification model and the entire learning framework is needed.

To have a general comparison between different classification models for this problem, we test logistic regression and support vector machine by adjusting their thresholds. In this test, we find that both the classifiers are able to decrease the running time drastically with little loss in objective function value. A pruning rate of 60-70% resulted in a significant reduction in running time while increasing the objective function only slightly. While the general trends are similar across the two classifiers, SVM gives a better trade-off between the objective function value and running time. The comparison is shown in Figure 1.

As noted in Figure 1, both classifiers obtained a drastic reduction in running time at little loss in objective function value. This effect is further illustrated in Table 2, which presents the results of the learning-to-prune approach on the 10 test instances using the SVM classification model. We first note that on these larger and more complex instances, the time to compute all the features including the LP values is very small compared to the time to run the original ILP. More importantly, the running time of the learning-to-prune approach (including the time to compute features and then running the ILP with hard pruning constraint) is around 99% less than the original ILP solver time on these instances (using the Gurobi solver). In 7 of these 10 instances, the hard pruning is able to find the optimal solution itself in significantly less time. In the remaining three instances, the resultant increase in the objective function value because of the mistakes in the pruning process is still very small (less than 0.6%).

In applications where we wish to reduce the optimality gap even further, we can use the soft pruning approach. The idea here is that instead of adding a hard constraint that no edge can be taken from the set of pruned edges (fixing those edge variables to 0), we add a soft constraint that a small constant number of edges can be taken from the set of pruned edges in the returned solution. In other words, we add the constraint that sum of all edge variables corresponding to pruned edges has to be less than equal to a small constant. This is implemented by simply adding the corresponding constraint in the ILP formulation. While the soft pruning still retains all the edge variables in the ILP formulation, it prunes the search space considerably. When applied on the instance i160-344, the soft pruning approach, that allows just one edge from the pruned set, finds the optimal solution of the original problem. The running time of this approach on this instance is around 3000 seconds, which is still considerably less than the original ILP time of around 27000 seconds, but more than the time of the hard pruning approach (around 150 seconds).