1

I am looking at the dual solution obtained for the minimum spanning tree problem. How can I extract the information on which edges are included in the optimal solution?

The dual formulation that I am using is;

$ \begin{align} ~\max &~ z (|V|-1) + \sum_{S \subseteq V : |S| \neq \emptyset} (|S|-1) y_{s} \\ \label{DMST2} s.t. &~ z + \sum_{S: (i,j) \in E(S)}^{} y_{s} \leq w_{ij} & \forall (i,j) \in E \\ \label{DMST3} &~y_{s} \leq 0 & \forall S \subseteq V : |S| \neq \emptyset \end{align} $

Suppose I have the following toy graph with the adjacency matrix below.

$ \begin{bmatrix} {0, 20, 5, 5, 15} \\ {20, 0, 9, 8, 23} \\ {5, 9, 0, 8, 7} \\ {5, 8, 8, 0, 14} \\ {15, 23, 7, 14, 0} \end{bmatrix} $

Now, I look at the dual solution obtained after solving the model. First, let's see the subsets used to generate the dual constraints.

[{1} {2} {1 2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4} {5} {1 5} {2 5} {1 2 5} {3 5} {1 3 5} {2 3 5} {1 2 3 5} {4 5} {1 4 5} {2 4 5} {1 2 4 5} {3 4 5} {1 3 4 5} {2 3 4 5}]

The following solution is obtained from the dual.

{1 3} : $y_5 =-2$

{1 4} : $y_9 =-3$

{1 3 5} : $y_{21} =-1$

z = 8

For instance, how can I conclude that the edge {2-4} is in the optimal solution?

whitepanda
  • 196

1 Answers1

0

Apply complementary slackness in both directions: $$y_S < 0 \implies \sum_{(i,j) \in E(S)} x_{i,j} = |S| - 1 \tag1$$ and $$x_{i,j} > 0 \implies z + \sum_{S: (i,j) \in E(S)} y_S = w_{i,j}. \tag2$$

For example, $(1)$ and $y_5=-2<0$ imply that $x_{1,3}=1$. Similarly, $(1)$ and $y_9<0$ imply that $x_{1,4}=1$, which in turn implies $x_{3,4}=0$ from the primal constraint for $\{1,3,4\}$. Also, $(1)$ and $y_{21}<0$ imply that $x_{1,3}+x_{1,5}+x_{3,5}=2$.

You can also use the contrapositive of $(2)$ to deduce $x_{1,2}=x_{1,5}=x_{2,3}=x_{2,5}=x_{4,5}=0$, which implies that $x_{3,5}=1$.

Now the primal cardinality constraint yields $x_{2,4}=1$.

RobPratt
  • 45,619