Looking for Integer LP formalisation of k-MST

Question

I am looking for a Integer LP formalisation for the k-Minimum Spanning Tree problem.

My idea:

• x_ij = 1 means there is an edge from i to j in the tree.
• y_i = 1 means vertex i is part of the tree
• c_ij are the costs for the edge from i to j

objective function: min sum(x_ij*c_ij) for all i,j

constraints:

1. sum y_i = k (1)
2. sum(x_ij) for all j and some i >= yi (2)
3. sum(x_ji) for all j and some i >= yi (3)
4. 2*x_ij <= yi+yj

(1) makes sure that there are exactly k vertices in the MST. (2) and (3) make sure that if node i is in the tree at least one edge that contains that node is in the tree. (4) says that if there is an edge between i and j in the tree, then also the vertices i and j have to be in the tree.

Unfortunately that does not work as expected. Does anyone know my mistake?

Answer 1

You need to ensure that the subgraph chosen is connected.