Need Help Understanding MST Cutset Formulation

Question

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).

This is the definition:

An integer linear program that solves the minimum spanning tree problem is as follows:

$$ \begin{align*} \text{Minimize} & \sum_{\{u,v\} \in E} w_{u,v}x_{u,v} \\ \text{subject to} & \sum_{\substack{\{u,v\} \in E\colon \\ u \in S, v \notin S}} x_{u,v} \geq 1 & \text{for all $S \subseteq V$ with $0 < |S| < |V|$} \\ & \sum_{\{u,v\} \in E} x_{u,v} \leq |V|-1 \\ & x_{u,v} \in \{0,1\} & \text{for all $\{u,v\} \in E$} \end{align*} $$

$x_{ij}$ is defined to be $1$ if the edge $ij$ is in $T$.

What exactly does the optimum value represent here? Is it the number of edges that are used in our MST? If so, how does knowing the number of edges help us in forming the MST?

How does this ILP "work" to solve the MST problem?

Answer 1

The first constraint makes sure the induced subgraph remains connected : there must be an edge between every pair of subsets of $V$ ; or in terms of graph theory, for every cut, at least one edge must cross the cut. For example, if $S=\{a\}$, the constraint is $$ \sum_{(u,a)|u\neq a} x_{ua} \ge 1 $$ and this imposes that $a$ does not end up alone.

The second constraint makes sure you end up with $n-1$ edges, which is a characteristic of a tree.

Answer 2

The objective value of the integer program is the total weight of edges in the tree.

Here is how this integer program works:

1. The constraint $x_{uv} \in \{0,1\}$ allows us to consider the set $T = \{ uv : x_{uv} = 1 \}$.
2. The first constraint states that $T$ crosses every cut in the graph.
3. The second constraint guarantees that $T$ contains at most $|V|-1$ vertices.
4. The objective function is the total weight of edges in $T$.

Answer 3

Yuval has explained why and how that program by integer linear programming works.

I would like to point out that a simpler version of that program in the following. Please note, as usual and as in the question, we assume the graph is a connected graph.

$$ \begin{aligned} \text{Minimize} &\sum_{\{u,v\} \in E} w_{u,v}x_{u,v} \\ \text{subject to} &\sum_{\substack{\{u,v\} \in E\colon \\ u \in S, v \notin S}} x_{u,v} = 1 & \text{ for all } S \subseteq V \text{ with } 0 < |S| < |V| \\ & x_{u,v} \in \{0,1\} & \text{ for all } \{u,v\} \in E \end{aligned} $$

Here is a brief explanation why the above simpler program is correct.

1. The last constraint, $x_{u,v} \in \{0,1\} \text{ for all } \{u,v\} \in E$ indicates whether the edge $\{u,v\}$ is included or not. 1 means inclusion and 0 means exclusion.
2. The first constraint requires that for any given cut of the graph, the set of included edges must contain an edge that crosses that cut. That is, it must be a connected spanning subgraph. Since it never has more than one edge to cross the same cut, it does not contain a cycle. So it is actually a spanning tree. That is why we can do away with the second to last constraint in the original program.
3. The objective function is the total weight of included edges, which is a spanning tree. Since we want to minimize that objective function, we will find the minimum spanning tree.