I'm considering integer programming on an variation of Steiner Forest Problem:

Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive integer $k$, find a subgraph containing at most $k$ connected components that includes all the terminals with minimum total edge cost.

The key point of constructing the ingeger programming is to enforce the $k$ connected components constraint. The only way I came up with is using the generalized subtour elimination constraints over edge variables for each connected component. Is there any other ways to enforcing the $k$ connected components constraint? Any clue or suggestion would be appreciated.

  • 1
    $\begingroup$ How about adding a 0/1 variable $x_{\{u,v\}}$ for each nonedge $\{u,v\}\notin E$ and adding the constraint to select at most $k$ of them, that is, $\sum_{\{u,v\}\notin E} x_{\{u,v\}} \le k-1$? Any spanning forest with at most $k$ connected components can be connected via at most $k-1$ of these artificial edges of cost zero and vice versa. $\endgroup$ Sep 19, 2018 at 18:04
  • $\begingroup$ Let $C_1$, $\ldots$, $C_k$ be the components in an optimal solution. It is possible that all edges between $C_i$ and $C_j$, $i\ne j$ are in $E$? $\endgroup$
    – Yixin Cao
    Sep 26, 2018 at 2:07
  • $\begingroup$ @YixinCao It may be the case. My reply is too long to be a comment, please check my answer below. $\endgroup$
    – Mengfan Ma
    Sep 29, 2018 at 13:56

1 Answer 1


Base on Komus's constraint, we add another constraint which ensures a Steiner Tree on $G^{'}=(V, E^{'})$, where $E'=\{(i,j): i,j \in V\}$: $$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$where $cut(U,V)$ denotes the cut set of $(U,V)$.

Together with Komus's constraint, our model is obtained as follows:

$$min \sum_{e \in E}c_e x_e$$ subject to $$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$ $$\sum_{e \notin E} x_e \le k-1$$

Base on Cao's comment, one more step is needed to prune the solution of our model: if $\sum_{e \notin E}x_e < k-1$, then we delete the largest $\Delta$ edges in the solution, where $\Delta=k-1-\sum_{e \notin E}x_e$. Then we get an optimal solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.