IP model for k-rooted spanning forest

Question

I am looking for an IP model for finding a $k$-rooted minimum spanning forest on an undirected graph $G$.

Given a set of roots $R$ and a set of nodes $N$ $(R\cap N=\emptyset)$, I would find a forest of $k=|R|$ disjointed trees that span all nodes in $R \cup N$ where each $r \in R$ belongs to exactly one tree, and the sum of the edges in the trees is the minimum.

AFAIK, this is a well-known problem. However, I only found IP models for the (single) minimum spanning tree.

I tried to extrapolate a model from here, but to no avail (there are a few things I don't understand, and eventually my attempt does not avoid cycles).

I know that this is $\sf NP$-hard, but I would like to implement and test it on small instances.

Thanks

Answer 1

There are flow models for the MST problem that can easily be adapted to the $k$-rooted MST. For each edge $e=(i,j)$ in the graph, create a binary variable $x_e$ (1 if the edge is used in a tree, 0 if not) and two nonnegative variables $y_{ij}, y_{ji}$ representing flows along the edge in either direction. Connect them via the constraints $y_{ij} \le n x_e$ and $y_{ji} \le n x_e$ where $n = \vert N \vert$. The objective is to minimize the weighted sum of the $x_e$ variables.

Add a dummy source node to $G$ with supply $n$ and an arc with cost 0 and capacity $n$ to each node in $R$. Give each node in $N$ a demand of 1 and set up the usual flow conservation constraints. Note that there are no costs for flows, only the fixed costs for including the edges carrying the flows.

Answer 2

I recommend extending Paul's single-commodity formulation to a multicommodity formulation with $k$ commodities. Let binary variable $z_{i,r}$ indicate whether node $i\in R \cup N$ is assigned to tree $r\in R$. The idea is to send one unit of commodity $r$ from the dummy source node $0$ to node $i$ iff $z_{i,r}=1$. The problem is to minimize $\sum_e c_e x_e$ subject to \begin{align} \sum_r z_{i,r} &= 1 &&\text{for $i\in R \cup N$} \\ z_{r,r} &= 1 &&\text{for $r\in R$} \\ y_{i,j,r} + y_{j,i,r} &\le (n+1) x_e &&\text{for $e=(i,j) \in E$ and $r\in R$} \\ \sum_j (y_{j,i,r} - y_{i,j,r}) &= z_{i,r} &&\text{for $i \in R \cup N$ and $r \in R$} \\ \sum_j y_{0,j,r} &= \sum_i z_{i,r} &&\text{for $r \in R$} \\ \end{align} You can optionally include a cut $\sum_e x_e = n$ because a spanning forest on $n+k$ nodes with $k$ trees has $n$ edges.

Like the usual formulation for the minimum-cost multicommodity network flow problem, this formulation lends itself to Dantzig-Wolfe decomposition with one block per commodity.