Two minimum spanning trees

129 Views Asked by At

I have a problem with this exercise.

Consider a non-oriented graph $G=(N,E)$, with $n=|N|$ and weight $c_{i,j}$ associated to the edges $(i,j)$ in $E$.

  1. Consider a vertex $a$ in $N$. Write the ILP model to find two spanning trees of minimum total length, without common edges and such that one of them has the number of edges incident to $a$ exactly equal to 3.

  2. Consider now a set of vertices $S$ in $N$. Write the ILP model to find two spanning trees of minimum total length, without common edges and such that they touch the vertices of $S$ in a balanced way: incident edges to every vertex $a$ in $S$ used by one of the two trees cannot be greater than two times of edges used by other tree.

My attempt for the question 1.:let $x_{i,j}=1$ if I choose the edge $(i,j)$ for the tree $T_1$ and 0 otherwise. The same for the other tree $T_2$ with the labels $y_{i,j}$. This is my ILP model: \begin{align} &&\text{minimize} \sum_{(i,j) \in E} c_{i,j}(x_{i,j}+y_{i,j}) \\ &&\sum_{(i,j) \in E} x_{i,j} &= n-1 \\ &&\sum_{(i,j) \in E} y_{i,j} &= n-1 \\ &&\sum_{(i,j) \in E(S)} x_{i,j} &\leq |S| -1 && \text{for every $S\subseteq N$} \\ &&\sum_{(i,j) \in E(S)} y_{i,j} &\leq |S| -1 && \text{for every $S\subseteq N$} \\ &&x_{i,j}+y_{i,j}&\le 1 &&\text{for every $(i,j)\in E$} \\ &&\sum_{(i,j) \in \delta(a)} x_{i,j} &=3 \end{align}

where $E(S)=\{(i,j)\in E \,|\, i \in S\, , j \in S \}$ ; $\delta(a)=\{(i,j)\in E \,|\, i =a \text{ or } j = a \}$. The first four conditions are the classic conditions for minimum spanning trees to be connected and without cycles. The fifth condition is the fact that the trees have no common edges.

What do you think? What about the second question?

1

There are 1 best solutions below

1
On BEST ANSWER

I made several corrections to your formulation for the first question. The new constraints needed for the second question are \begin{align} \sum_{(i,j)\in \delta(a)} x_{i,j} &\le 2 \sum_{(i,j)\in \delta(a)} y_{i,j} &&\text{for $a\in S$} \\ \sum_{(i,j)\in \delta(a)} y_{i,j} &\le 2 \sum_{(i,j)\in \delta(a)} x_{i,j} &&\text{for $a\in S$} \end{align}