线性规划(2)：LP对偶的应用

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为LP对偶的应用，包括最大流最小割定理的证明。

最大流最小割定理

原问题与对偶问题

• 原问题：

$$\begin{align*} \text{maximize} &\quad \sum_{u:(s, u) \in E} f_{su} \\ \text{subject to} &\quad 0 \le f_{uv} \le c_{uv} &&\quad \forall (u, v) \in E \\ &\quad \sum_{v:(v, u) \in E} f_{vu} = \sum_{w:(u, w) \in E} f_{uw} &&\quad \forall u \in V \setminus \{s, t\} \end{align*}$$

• 对偶问题：

$$\begin{align*} \text{minimize} &\quad \sum_{(u, v) \in E} c_{uv} y_{uv} \\ \text{subject to} &\quad y_{su} + z_u \ge 1 &&\quad \forall u: (s, u) \in E \\ &\quad y_{vt} - z_v \ge 0 &&\quad \forall v:(v, t) \in E \\ &\quad y_{uv} - z_u + z_v \ge 0 &&\quad \forall (u, v) \in E, u \neq s, v \neq t \\ &\quad y_{uv} \ge 0 &&\quad \forall (u, v) \in E \end{align*}$$

• 对偶问题的理解：
  • $y_{uv} = 1$ 表示边 $(u, v)$ 是割边，$y_{uv} = 0$ 表示不是
  • $z_u = 1$ 表示 $u$ 在 $s$ 一边，$z_u = 0$ 表示 $u$ 在 $t$ 一边
  • 该对偶问题是分数形式的最小割问题

证明对偶问题有整数最优解

• 核心思路：证明多面体 $P = \{\bm{x}: A\bm{x} \le \bm{b}\}$ 的所有顶点均为整数点
• 定理：如果 $A \in \mathbb{R}^{m \times n}$ 是全单模（totally unimodular）矩阵，$\bm{b}$ 是整数向量，那么多面体 $P = \{\bm{x}: A\bm{x} \le \bm{b}\}$ 的顶点均为整数
  • 如果矩阵 $A$ 的任何子方阵的行列式都等于$0$，$1$ 或 $-1$，那么 $A$ 是全单模矩阵
  • 性质：如果 $A$ 是全单模矩阵，那么 $A^T, \begin{bmatrix}I & A\end{bmatrix}, \begin{bmatrix}A & I\end{bmatrix}, \begin{bmatrix}I \\ A\end{bmatrix}, \begin{bmatrix}A \\ I\end{bmatrix}$ 都是全单模矩阵
• 归纳法证明：

注：本文中所有图片均来自张宇昊老师的课程PPT。