# Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

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.

• 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. Sep 19 '18 at 18:04
• 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$? Sep 26 '18 at 2:07
• @YixinCao It may be the case. My reply is too long to be a comment, please check my answer below. Sep 29 '18 at 13:56

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)$$.
$$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.