Linear Programming & Simplex Method
翻了两本书和四五篇论文的笔记总和……
Linear Programming & Simplex Method
Linear Programming
Optimization goal 最优化目标:某个线性函数值。
Subject to 限制于:线性等式或不等式组。
Namely 形式化:
$$ \begin{align} \max (\min) ~&\bold c^T\bold x \\ \text{s.t.} ~ &\bold A \bold x\le(=/\ge) \mathrm {\bold b} \\ & \bold x \ge \bold0 \end{align} $$
Standard Form
$$ \begin{align} \max~ &\bold c^T\bold x\\ \text{s.t.} ~& \bold A\bold x\le \bold b \\ &\bold x \ge \bold0 \end{align} $$
Relaxation
$$ \begin{align} \max ~& \bold c^T\bold x \\ \text{s.t.} ~& \bold A\bold x=\bold b \\ & \bold x\ge \bold 0 \end{align} $$
Transformation
With Minimum Goal
$$ \min \bold c^T\bold x \Leftrightarrow-(\max\bold {(-c)}^T \bold x) $$
With Equality Condition
$$ \sum_j a_{i,j} x_j=b_i \Leftrightarrow \begin{cases} \sum_j a_{i,j}x_j\le b_i \\ \sum_ja_{i,j}x_j\ge b_i \end{cases} $$
With Greater Inequality Condition
$$ \sum_j a_{i,j}x_j\ge b_i \Leftrightarrow \sum_j (-a_{i,j})x_j\le-b_i $$
Without Non-negative Constraint
$$ x_i \not \ge 0 \Leftrightarrow \begin{cases} x_i \leftarrow x_{i1}-x_{i2} \\ x_{i1},x_{i2} \ge 0 \end{cases} $$
From Standard Form To Relaxation
$$ \sum_j a_{i,j}x_j\le b_i \to \sum_j a_{i,j}x_j+x_{n+i}=b_i, x_{n+i} \ge 0 $$
Some Examples
Ex. (最短路) $ n $ 点 $ m $ 边带权无向图,求 $ s $ 到 $ t $ 最短路。
M. $ \min \{d_t:d_s=0, d_{v,i} \le d_{u,i}+w_{u,v}, \forall (u,v)\in E\} $ .
Ex. (最优资源配置) $ m $ 资源 $ n $ 项目,每个资源上限 $ b_j(1\le j\le m) $. 第 $ i $ 个项目做出 $ x_i $ 的成果量,可获得 $ c_ix_i $ 的收益,同时消耗第 $ j $ 种资源 $ a_{i,j}x_i $ . 求最大收益.
M. $ \max\{c_ix_i:\sum_{i=1}^n a_{i,j} x_i\le b_j,1\le j\le m; x_i\ge 0,1\le i\le n \} $ .
Ex. (最佳物资供给) $ m $ 需求. 对 $j $ 需求需要 $ b_j $ 的资源. 有 $ n $ 种物资,其中第 $ i $ 种可以给第 $ j $ 种需求 $ a_{i,j} $ 的量. 假设第 $ i $ 种物资供给了 $ x_i $ 单位,需支付费用 $ c_ix_i $ . 最小化总费用.
M. $\min\{ c_ix_i:\sum_{i=1}^ma_{i,j}x_j\ge b_j,1\le j\le m;x_i\ge 0,1\le i\le n \}$ .
Ex. (多物网络流) $ n $ 点有向图,$ i $ 到 $ j $ 流量限制为 $ l_{i,j} $ . 现有 $ p $ 商品线路,第 $ i $ 条从 $ s_i $ 向 $ t_i $ 运输 $ d_i $ 个商品,求是否存在可行解.
M. $\max\{ 0:f_{k,u,v}\le l_{u,v},\sum_kf_{k,u,v}\le l_{u,v}, f_{k,u,v}=-f_{k,v,u},\sum_if_{k,u,i}=0,\sum_i f_{k,s_i,v}=d_i \}$ .检查是否有解即可.
N. 该问题不存在 LP 意外的高效做法.
Simplex Method
在松弛型中,称 $ (x_i)_{i=1}^n $ 为非基变量,赋初值为 $ 0 $ ;称 $ (x_i)_{i=n+1}^{n+m} $ 为基变量,赋初值为 $ b_{i-n} $ .
易看出当 $ (b_i)_{i=1}^n \ge 0 $ 时此初始状态为可行解,考虑找出两个交换可以优化的变量,执行转轴。
Pivot(l, e)
交换基变量 $ x_{n+l} $ 与非基变量 $ x_e $ 的表达式,使得二者位置互换。
$$ x_{n+l}=b_l-\sum_ja_{i,j}x_j \\ x_e={1\over a_{l,e}}(b_l-\sum_{j\neq e}a_{l,j}x_j-x_{n+l}) $$
交换下标。若需记录方案则多记录一下原来对应的下标。
Optimization
优化基础可行解。
- 选 $ x_e : c_e\ge 0 $ ;
- 找 $ x_{n+l} : a_{l,e}>0,\max {b_l \over a_{l,e}} $ ;
- pivot(l, e);
- 重复 1°.
算法停止,当且仅当
- 找不出 $ e $ ,此时满足各条件;
- 找不出 $ l $ ,此时无界,最优解为 $ +\infty $ .
该算法自然是完备的。
Initialization
以上我们假定了 $ \forall b_i\ge 0 $ ,如果没有这个条件,我们需要引入一个辅助 LP 来确定初值。
$$ \begin{align} \max ~&-x_0 \\ \text{s.t.} ~& x_{i+n}=b_i-\sum_j a_{i,j}x_j+x_0 \\ & x_i \ge 0 \end{align} $$
这种构造使得这个新 LP 问题使用上述过程必然可以找到一组可行解(只要存在;如果不存在那么可行域必为空)。
可知当 $ x_0=0 $ 时,各初解满足,可以开始执行前述二过程找最优解。
Complexity
只需分析 pivot 的执行次数。这是 $ \mathcal O{n+m\choose n} $ 的. 空间是 $ \mathcal O(nm) $ 的. 差不多可以认为 $ \mathcal O($存的下$)=\mathcal O($跑得过$) $ .
LP on Network Flow
Maxflow
$$ \begin{align} \max ~&\sum_v f_{s,v}\\ \text{s.t.} ~&\sum_v f_{u,v}-\sum_vf_{v,u}=0\\ &f_{u,v}\le c_{u,v}\\ &f_{u,v}\ge 0 \end{align} $$
分别是流量平衡条件,流量限制,流量非负.
Mincost Maxflow
同上,将目标函数修改为 $ \min \sum_{(u,v)\in E}f_{u,v}w_{u,v} $ 即可.
Maximum Bipartite Matching
$$ \begin{align} \max ~& \sum_{x\in X,y\in Y} f_{x,y} \\ \text{s.t.}~&\sum_{u\in X} f_{u,v}\le 1 \\ &\sum_{v\in Y} f_{u,v} \le 1 \end{align} $$
Maximum Weight Bipartite Matching
同上,目标函数改为 $ \max \sum_{x\in X,y\in Y} f_{u,v}w_{u,v} $ .
Duality
有时候考虑对偶问题有助于我们更好的分析问题的性质和建模。
对偶:将约束视为变量,约束之间的关系视为新的约束,形式化说来
$$ \begin{align} &(\text {LP})\min \{\bold c^T\bold x: \bold A\bold x\le\bold b,\bold x\ge 0,\bold x\in\mathbb R^n\} \\ &(\text {LD})\max \{\bold b^T\bold y: \bold A^T\bold y\ge\bold c, \bold y\ge 0,\bold y\in\mathbb R^m \} \end{align} $$
(LP) 与 (LD) 互为对偶问题. 并且显然 $ \text{opt(LP)}\ge \text{opt(LD)} $ . 更进一步我们有
Theorem(强对偶定理) 当存在最优解,上式等号恒成立.
有些性质和总结
- 原问题的变量对应对偶问题的约束条件;
- 原问题的约束条件对应对偶问题的变量;
- 原问题与对偶问题的目标函数方向相反;
- 原问题无约束对应对偶问题变量为零,反之亦然;
- 对偶问题的对偶问题是原问题.
Some Examples
最大流最小割 假设汇点回流到源点,我们有 $ \max \{f_{t,s} : f_{u,v}\le c_{u,v},\sum_v f_{u,v}=\sum_vf_{v,u},f_{u,v}\ge0 \} $ .
令 $ p_u:=[u\in S], d_{u,v}:=\max\{p_u-p_v,0\} $ ,则最小割为 $ \min\{ \sum_{(u,v)\in E} c_{u,v}d_{u,v}:d_{u,v}-p_u+p_v\ge 0,p_s-p_t\ge 1,p_u,d_{u,v}\in \{0,1\} \} $ .
最大流的对偶问题是 $ \min\{ \sum_{(u,v)\in E} c_{u,v}d_{u,v}:d_{u,v}-p_u+p_v\ge0,p_s-p_t\ge1,d_{u,v}\ge0 \} $ .
据说可以证得一定存在最优解使得 $ p_u\in\{0,1\} $ ,这样就证明了最大流最小割定理了.
二分图最大匹配最小点覆盖 二分图最大匹配 $ \max\{\sum_{u\in X,v\in Y} f_{u,v} : \sum_{u\in X}f_{u,v}\le1,\sum_{v\in Y}f_{u,v}\le1 \} $ .
对偶问题为 $ \min\{\sum_{u\in X}p_u+\sum_{v\in Y}p_v:p_u+p_v\ge1,p_u,p_v\ge0 \} $ .
二分图最大权匹配最小顶标和 二分图最大权匹配 $ \max\{ \sum_{u\in X,v\in Y} c_{u,v}f_{u,v} :\sum_{x\in X}f_{u,v}\le1,\sum_{v\in Y} f_{u,v}\le1 \} $ .
对偶问题为 $ \min\{ \sum_{u\in X}p_u+\sum_{v\in Y}p_v :p_u+p_v\ge w_{u,v}, p_u,p_v\ge0 \} $ .
Integer Programming
考虑取值范围为整数的整数规划问题 Integer Programming 及其对偶
$$ \begin{align} &(\text {IP})\min \{\bold c^T\bold x: \bold A\bold x\le\bold b,\bold x\ge 0,\bold x\in\mathbb Z^n\} \\ &(\text {ID})\max \{\bold b^T\bold y: \bold A^T\bold y\ge\bold c, \bold y\ge 0,\bold y\in\mathbb Z^m \} \end{align} $$
因为 (IP) 比 (LP) 紧,所有应该有 $ \text{opt(LP)}\le\text{opt(IP)} $ ,考虑对称性和强对偶定理,则一般我们有
$$ \text{opt(ID)}\le\text{opt(LD)}=\text{opt(LP)}\le\text{opt(IP)} $$
虽然有看起来不错的性质,但是
Theorem 求解整数规划问题是 NP-hard 的.
那么我们只考察一些特殊情况.
Totally Unimodular Matrix
全幺模矩阵指该矩阵的任意一个行列数相等的满秩的子矩阵的行列式值都为 $ \pm 1 $ . $ A $ 是全幺模的一个充分条件为
- $ A $ 全由 $ -1,0,1 $ 构成;
- $ A $ 每列最多包含两个非零数;
- $ A $ 的行可以被划分为两个集合 $ B,C $ ,若有一行包含相同符号的非零数则被分在不同集合,否则相同.
一个我们更为关心的性质是如果一个 LP 的系数矩阵是全幺模的,那么单纯性涉及到的所有约束系数都是 $ -1,0,1 $ 之中一个,也即 LP 与 IP 得到的解在这种情况下是相同的.
某些非常特殊的 DP 和所有网络流问题的约束矩阵都是全幺模的.
LP on Game Theory
来看看 LP 在博弈论里的用处.
Nash Equilibrium
Nash 均衡指在二人或多人博弈中的这样一种状态,任何一方单方面更改策略都不能使自己获得更高收益.
如果在一个策略组合中,每个人的策略都是固定的,那么称此为纯策略 Nash 均衡. 如果每个人的策略是以一定概率组合起来的,则称混合策略 Nash 均衡.
Theorem 对于任意一个决策数有限的零和博弈,存在至少一个混合策略 Nash 均衡.
那么这种情况就可以将问题转化为可以用 LP 来做了.
1 这是啥书的内容啊
2 LP目前最优算法的时间复杂度是多少 就是单纯形那个吗?
3 也就是说系数矩阵为全幺模矩阵时,LP的解(若有)则一定为一定为整数咯?这种情况下,用IP的分支定界法(branch and bound)和用LP的单纯形法求解哪个会更快些?
1 《算法导论》、《挑战程序设计竞赛》、《算法艺术与信息学竞赛》及其学习指导,还有2015年和之前的国家集训队的几篇论文……可能还有基本组合最优化的书我甚至都忘了名字……
2 有椭球算法($ \mathcal O(n^6L^2) $)和内点算法($ \mathcal O(n^{3.5}L^2) $),以及其他更为现代的算法。但是效率上都不及单纯形。事实上人们很长时间怀疑 LP 不是多项式时间可解的。
3 更为准确的说法是必有整数解在其解集内。我没有研究过分治定界法(捂脸)但在可以容忍的范围内单纯形还是很有效率的。所以我站单纯形。(实际上后者也是指数时间的话这么比较也没什么意思,其实是我不会 time complexity)