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

<p>Together with Komus's constraint, our model is obtained as follows:</p>

<blockquote>
  <p><span class="math-container">$$min \sum_{e \in E}c_e x_e$$</span>
  subject to 
  <span class="math-container">$$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$</span>
  <span class="math-container">$$\sum_{e \notin E} x_e \le k-1$$</span></p>
</blockquote>

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

CC BY-SA 4.0
2018-09-29T13:54:45.070Z
2018-10-02T09:17:09.613Z
2018-10-02T09:17:09.613Z
Mengfan Ma
<p>I'm considering integer programming on an variation of Steiner Forest Problem:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 4.0
2018-09-19T18:04:43.543Z
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.
Christian Komusiewicz
CC BY-SA 4.0
2018-09-26T02:07:13.740Z
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$?
Yixin Cao
CC BY-SA 4.0
2018-09-29T13:56:26.930Z
@YixinCao It may be the case. My reply is too long to be a comment, please check my answer below.
Mengfan Ma
<integer-programming>
Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?
Mengfan Ma
# Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

(Asked by: username_0 on 2018-09-19)

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.

**Tags:** integer-programming
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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$?  
> **username_0**: @YixinCao It may be the case. My reply is too long to be a comment, please check my answer below.  

---

## 1 answers

### Answer by username_0 on 2018-09-29. Score: 2 | Accepted answer

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.


---

