Totally Unimodularity and Network Flows
2.1 Properties of Easy Problems
考虑一个有\(n\)个节点和\(m\)条边（\(m \ge n\)）的图\(G = (V, E)\)。如果算法在最坏情况下需要\(O(m^p)\)次基本计算，则图的算法是有效的。
Separation Problem：对于COP (Combinatorial optimization problem)问题\(\max\{ \mathbf{c^T x} \mid \mathbf{x} \in X \subseteq \mathbb{R}^n \}\)，给定\(\mathbf{x}^* \in \mathbb{R}^n\)，\(\mathbf{x}^* \in \operatorname{conv}(X)\)？如果不是，那么可以找到一个割平面\(\pmb{\pi}^T \mathbf{x} \le \pmb{\pi}_0\)将\(X\)和\(\mathbf{x}^*\)分开。
简单问题 \(\text{(P)} \ \max\{ \mathbf{c^T x} \mid \mathbf{x} \in X \}\)的四个性质：
- Efficient optimization property：(P)存在一个有效的算法。
- Strong duality property：存在一个强对偶问题\(\text{(D)} \ \max\{ w(\mathbf{u}) \mid \mathbf{u} \in U \}\)，用它可以快速地检验最优条件：如果存在\(\mathbf{u}^* \in U\)使得\(\mathbf{c^T x^*} = w(\mathbf{u}^*)\)，那么\(\mathbf{x}^* \in X\)是(P)的最优解。
- Efficient separation property：对于相关的分离问题，存在一种有效的算法。
- Explicit convex hull property：已知\(\operatorname{conv}(X)\)的紧描述，那么(P)等价于线性规划\(\max\{ \mathbf{c^T x} \mid \mathbf{x} \in \operatorname{conv}(X) \}\)。
2.2 Totlly Unimodular Matrix
考虑线性整数规划：
\[\text{(IP)} \qquad \begin{aligned} \min \quad & \mathbf{c^T x} \\ \text{s.t.} \quad & \mathbf{Ax \le b} \\ & \mathbf{x} \ge 0, \ \mathbf{x} \text{ integer}. \end{aligned}\]令\(X = \{ \mathbf{x} \mid \mathbf{Ax \le b}, \ \mathbf{x} \in \mathbb{Z}_+^n \}\)。考虑如下线性规划：
\[\text{(LP)} \qquad \begin{aligned} \min \quad & \mathbf{c^T x} \\ \text{s.t.} \quad & \mathbf{Ax \le b}, \ \mathbf{x} \in \mathbb{R}_+^n . \end{aligned}\]问：(LP)的可行域（polyhedron）中所有的极值点都是整数吗？
充分条件：如果\((\mathbf{A, I})\)的最优基\(\mathbf{B}\)满足\(\det(\mathbf{B}) = \pm 1\)，那么(LP)与(IP)等价。 \((\mathbf{A, I}) = (\mathbf{B, N})\)，(LP)的最优解\(\mathbf{x} = (\mathbf{B^{-1}b, 0})\)。
（Cramer's rule：\(\mathbf{B}^{-1} = \mathbf{B}^* \det(\mathbf{B})\)，其中\(\mathbf{B}^*\)是\(\mathbf{B}\)的伴随矩阵。）
Totally unimodular matrix：如果一个矩阵\(\mathbf{A}\)的每个平方子矩阵都有行列式+1，-1或0，那么矩阵\(\mathbf{A}\)是全单模矩阵。
如果\(\mathbf{A}\)是全单模矩阵，那么\(a_{ij} \in \{ +1, -1, 0 \}\)。
\(\mathbf{A}\)是全单模矩阵，当且仅当\(\mathbf{A^T}\)是全单模矩阵或\((\mathbf{A, I})\)是全单模矩阵。
判断全单模矩阵的充分条件：
\(\mathbf{A}\)是全单模矩阵，如果
（1）\(a_{ij} \in \{ +1, -1, 0 \}\)（矩阵元素全为+1，-1或0）；
（2）\(\sum_{i=1}^m |a_{ij}| \le 2\)（每行最多有两个非零元素）；
（3）存在分割可以按行\(\{1, 2, \ldots, m\}\)将矩阵分成两部分\((M_1, M_2)\)，使得包含两个非零系数的每一列\(j\)满足\(\sum_{i \in M_1} a_{i j}=\sum_{i \in M_2} a_{i j}\)。
证：假设\(\mathbf{A}\)不是TU的，\(\mathbf{B}\)为\(\mathbf{A}\)的最小子方阵且有\(\det(\mathbf{B}) \neq 0, 1, -1\)。\(\mathbf{B}\)不可能包含只有一个非零项的列（否则\(\mathbf{B}\)将不是最小的）。所以\(\mathbf{B}\)的每一列都有两个非零项。通过加上\(M1\)中的行，减去\(M2\)中的行，可以得到零向量，所以det(B) = 0，这是矛盾的。
线性规划\(\max \{ \mathbf{c^T x} \mid \mathbf{Ax} \le \mathbf{b}, \mathbf{x} \in \mathbb{R}_+^n \}\)对所有的整数\(\mathbf{b}\)都有一个整数最优解，对于这个整数\(\mathbf{b}\)有一个有限的最优值，当且仅当\(\mathbf{A}\)是TU。
强对偶性质、显式凸包和有效分离性质当\(\mathbf{A}\)是TU时都成立。
2.3 Minimum Cost Network Flows
2.4 Dijkstra Algorithm for Shortest Path Problem
2.5 Ford-Fulkerson Algorithm for Max-flow Problem
2.6 Minimum Spanning Tree and Minimum Steiner Tree
