patternMinor
Need Help Understanding MST Cutset Formulation
Viewed 0 times
understandingneedhelpcutsetmstformulation
Problem
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?
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?
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#99232, answer score: 3
Revisions (0)
No revisions yet.