Advanced Algorithms UE 9

by Maarten Behn
Group 5

Exercise 9.1 (MST Modeling and Separation) (8 Points)

Consider the Minimum Spanning Tree (MST) problem over a graph $G=(V,E)$ with edge costs $c_e$ and variables $x_e\in \{0,1\}$ indicating whether edge e is in the solution.

Use the so-called subtour elimination constraint
$\sum _{e\in E(S)}{x}_e\le |S|-1\forall S\subset V,2\le |S|\le |V|-1$
and one global constraint:
$\sum _{e\in E}{x}_e=|V|-1$
(a) Give an ILP formulation for the MST problem and argue why it is correct.

Variables:

$x_e\in \{0,1\}\forall e\in E$

Optimization function

$$min\sum _{e\in E}{c}_e{x}_e$$

Constraints

$\sum _{e\in E(S)}{x}_e\le |S|-1\forall S\subset V,2\le |S|\le |V|-1$

$\sum _{e\in E}{x}_e=|V|-1$
$x_e\in \{0,1\}\forall e\in E$

Argument why the IPL correct is

Feasibility enforces spanning trees:

• The cardinality constraint guarantees that the selected edges form a subgraph with exactly $|V|-1$ edges.

• The subtour elimination constraints prevent any cycle from forming in any subset $S$ of vertices. Since any cycle would violate the inequality

$$\sum _{e\in E(S)}{x}_e\le |S|-1,$$

no cycles can exist in the chosen edge set.

Connectivity is ensured implicitly:

• Given that the graph has $|V|$ vertices and $|V|-1$ edges, and no cycles are allowed (due to subtour constraints), the selected edges form a forest.

• Since the cardinality is exactly $|V|-1$ edges, the forest cannot be disconnected (a disconnected forest would have fewer than $|V|-1$ edges).

• Therefore, the selected edges form a connected acyclic subgraph — i.e., a spanning tree.

3. Optimality of the solution:

• By minimizing the sum of costs

$$\sum _{e\in E}{c}_e{x}_e,$$

the ILP finds the spanning tree with minimum total edge cost.

(b) Give a polynomial-time separation algorithm for the LP-relaxation of your ILP.
Hint: Use your knowledge about flow or cut problems.

We want to separate the subtour elimination constraints from a given fractional solution $\mathbf{x}=(x_e{)}_{e\in E}$ of the LP-relaxation, where $x_e\in [0,1]$.
That is, we want to check if there exists any subset $S\subset V$ with $2\le |S|\le |V|-1$ such that

$$\sum _{e\in E(S)}{x}_e>|S|-1,$$

which would violate the subtour elimination constraint.

Note that

$$\sum _{e\in E(S)}{x}_e\le |S|-1$$

is equivalent to

$$\sum _{e\in \delta (S)}{x}_e\ge 1,$$

where $\delta (S)$ are the cut edges of $S$.

The total number of edges inside $S$ plus the edges crossing the cut $\delta (S)$ relate to the degrees and connectivity. Since ${\sum }_{e\in E}{x}_e=|V|-1$, the subtour elimination can equivalently be detected by cuts of low $x_e$-weight.

Therefore the subtour elimination constraints can be replaced by cut constraints:

$$\sum _{e\in \delta (S)}{x}_e\ge 1,\forall S\subset V,S\ne \varnothing ,V.$$

Goal of the Algorithm

Given fractional values $x_e$, find a subset $S$ such that

$$\sum _{e\in \delta (S)}{x}_e<1.$$

If such a set $S$ exists, then the constraint corresponding to $S$ is violated.

Algorithm

Input: fractional solution $x_e\in [0,1]$.

• For each vertex $v\in V$:

  • Construct graph with edge capacities $c_e=x_e$.
  • For each other vertex $w\ne v$, compute the minimum $v$-$w$ cut.
  • If min cut value $<1$, output the cut $S$ inducing the violation.

• If no cut with capacity < 1 found, no subtour elimination constraint is violated.

Proof

• The minimum cut problem can be solved in polynomial time via max-flow algorithms.

• Since the number of vertices is $|V|$, and for each $v$ we consider cuts to all other vertices, the total number of max-flow computations is polynomial (at most $|V|\times (|V|-1)$).

• Each violated subtour elimination corresponds to a cut with capacity less than 1.

• This separation algorithm finds such cuts efficiently or confirms no violations exist.

Source of the Idea

https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture9and10.pdf (22.06.2025, 21:37)

Exercise 9.2 (Total Unimodularity) (4 Points)

Let $G=(V,E)$ be a bipartite graph.
Prove that the node-edge incidence matrix of $G$ is totally unimodular.
Hint: Use one of the properties stated in class.

Setup

Let $M\in \{0,1{\}}^{|V|\times |E|}$ node-edge incidence matrix of $G$.
$m_{v,e}=1$ $e$ is indecent to $v$ and $0$ is it is not.
$M$ is in row (the vertices), column (the edges) order.

Let $V_1,V_2\subseteq V$ be the two sides of the bipartite Graph.
(all edges have one vertex in $V_1$ and one in $V_2$)

Observation

An edge is always connected to two vertices.
$\Rightarrow \forall e\in E\sum _{v\in V}{m}_{v,e}=2$
⇒ Every column in $M$ contains two ones.

Characteristics of determiant

from Mathe 1 Course

Given a quadratic Matrix $M$
construct $M^{\prime }$ from $M$ by multiplying $k$ rows by $-1$ then:

$$det(M^{\prime })=(-1{)}^k\cdot det(M)=\{\begin{array}{ll}det(M)& \text{if}k\mid 2\\ -det(M)& \text{if}k\nmid 2\end{array}$$

Proof:
https://proofwiki.org/wiki/Determinant_with_Row_Multiplied_by_Constant?utm_source=chatgpt.com

Proof

Let $A$ be quadratic sub matrix of $M$.
Construct $A^{\prime }$ from $A$ by multiplying all rows belonging to vertices from $S_2$ by $-1$.
Now every column in $A^{\prime }$ contains at most one $+1$ and one $-1$.
The Lemma by Poincar´e states that $A^{\prime }$ is unimodular.
Then $A$ is also unimodular because multiplying rows $-1$ does not change the fact that the $det(A)\in \{-1,0,1\}$.

Exercise 9.3 (Complementary Slackness) (8 Points)

Dualize the following LPs and test with complementary slackness whether the given solutions are optimal.

Primal LP (P):

$$\begin{array}{rlr}\text{max }& x_1+3x_2+x_3& \\ \text{s.t. }& x_1+2x_2+7x_3\le -3& \text{1. Constraint}\\ & x_2-x_3=9& \text{2. Constraint}\\ & 9x_1\le 5& \text{3. Constraint}\\ & x_1\ge 0& \text{4. Constraint}\\ & x_2\le 0& \text{5. Constraint}\end{array}$$

Dual variables:

• $y_1$ for constraint 1 ($\le$): $y_1\ge 0$
• $y_2$ for constraint 2 ($=$): unrestricted
• $y_3$ for constraint 3 ($\le$): $y_3\ge 0$

Dual LP (D):

$$\begin{array}{rl}\text{min }& -3y_1+9y_2+5y_3\\ \text{s.t. }& y_1+9y_3\ge 1\\ & 2y_1+y_2\ge 3\\ & 7y_1-y_2\ge 1\\ & y_1\ge 0,y_3\ge 0,y_2\in \mathbb{R}\end{array}$$

Given Primal Solution:

$$x=(0,0,-9{)}^T$$

1. $x_1+2x_2+7x_3=0+0+7(-9)=-63\le -3$
2. $x_2-x_3=0-(-9)=9$
3. $9x_1=0\le 5$
4. $x_1=0\ge 0$
5. $x_2=0\le 0$
   All constraints are satisfied

Given Dual Solution:

$$y={\left(\frac{4}{9},\frac{19}{9},\frac{1}{9}\right)}^T$$

1. $y_1+9y_3=\frac{4}{9}+9\cdot \frac{1}{9}=\frac{13}{9}>1$
2. $2y_1+y_2=2\cdot \frac{4}{9}+\frac{19}{9}=\frac{27}{9}=3$
3. $7y_1-y_2=7\cdot \frac{4}{9}-\frac{19}{9}=\frac{28-19}{9}=1$
4. $y_1=\frac{4}{9}\ge 0$
5. $y_3=\frac{1}{9}\ge 0$
   All constraints are satisfied

Complementary Slackness Fails:

• Constraint 1 is slack ($-63<-3$) → $y_1=0$ → No
• Constraint 3 is slack ($9x_1=0<5$) → $y_3=0$ → No

Primal and dual feasible, but complementary slackness fails, so the solutions are not optimal.

b)

Primal LP (P):

$$\begin{array}{rlr}\text{min }& 5x_1+6x_2& \\ \text{s.t. }& 3x_1-x_2\ge 8& \text{1. Constraint}\\ & 2x_1+4x_2=-2& \text{2. Constraint}\\ & 3x_1+2x_2\le 4& \text{3. Constraint}\\ & x_{1\ge 0}& \text{4. Constraint}\end{array}$$

Dual variables:

• $y_1$ for constraint 1 ($\ge$): $y_1\ge 0$
• $y_2$ for constraint 2 ($=$): unrestricted
• $y_3$ for constraint 3 ($\le$): $y_3\le 0$

Dual LP:

$$\begin{array}{rl}\text{max }& 8y_1-2y_2+4y_3\\ \text{s.t. }& 3y_1+2y_2+3y_3\le 5\\ & -y_1+4y_2+2y_3\le 6\\ & y_1\ge 0,y_3\le 0,y_2\in \mathbb{R}\end{array}$$

Given Primal Solution:

$$x={\left(\frac{15}{7},-\frac{11}{7}\right)}^T$$

1. $3x_1-x_2=3\cdot \frac{15}{7}-(-\frac{11}{7})=\frac{45+11}{7}=\frac{56}{7}=8$
2. $2x_1+4x_2=2\cdot \frac{15}{7}+4\cdot (-\frac{11}{7})=\frac{30-44}{7}=-2$
3. $3x_1+2x_2=3\cdot \frac{15}{7}+2\cdot (-\frac{11}{7})=\frac{45-22}{7}=\frac{23}{7}\approx 3.29\le 4$
4. $x_1=\frac{15}{7}\ge 0$

All constraints are satisfied

Given Dual Solution:

$$y={\left(\frac{4}{7},\frac{23}{14},0\right)}^T$$

1. $3y_1+2y_2+3y_3=3\cdot \frac{4}{7}+2\cdot \frac{23}{14}=\frac{12}{7}+\frac{46}{14}=\frac{12+23}{7}=\frac{35}{7}=5$
2. $-y_1+4y_2+2y_3=-\frac{4}{7}+4\cdot \frac{23}{14}=-\frac{4}{7}+\frac{92}{14}=-\frac{4}{7}+\frac{46}{7}=\frac{42}{7}=6$
3. $y_1=\frac{4}{7}\ge 0$
4. $y_3=0\le 0$

All constraints are satisfied

Complementary Slackness passes:

• Constraint 1 is tight → $y_1$ can be $\ne 0$
• Constraint 2 is tight → $y_2$ unrestricted
• Constraint 3 is slack → $y_3=0$
• Variable $x_1=\frac{15}{7}\ne 0$, so dual constraint 1 must be tight
• Variable $x_2=-\frac{11}{7}\ne 0$, so dual constraint 2 must be tight

Primal and dual feasible, complementary slackness holds, so the solutions are optimal.