3
$\begingroup$

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.

$\endgroup$
  • 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$ – C Komus Sep 19 '18 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 '18 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 '18 at 13:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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