应用与计算数学

离散优化

在有限或可数的选择集合上进行优化,例如排班或路径规划问题。

直观什么是离散优化?

设想你要为一辆送货卡车选择路线,为工人排班,或者选出一部分要资助的项目。与光滑曲线不同,这里的选择以不可再分的整体单位出现:卡车要么经过某条街道要么不经过,工人要么值班要么不值班。离散优化就是在一个由 $n$ 个有限(或可数)离散可能性组成的集合中,寻找最优选择的数学,而不是沿着一条曲线连续滑动。

一个配送网络:节点是停靠点,边是带成本的道路。高亮显示的路径展示了有限多条可能路线中的一个离散选择。

中学从连续到离散:选择整数解

定义: 整数线性规划(ILP)

整数线性规划是在线性约束 $Ax \le b$ 下最大化线性目标函数 $c^T x$ 的问题,其中每个决策变量必须是非负整数: $x \in \mathbb{Z}^n_{\ge 0}$ 。许多实际问题——购买多少辆卡车、选择哪些项目——本质上就是整数问题,因此简单地对连续解四舍五入是不够好的。

\max\ c^T x \ \text{s.t.}\ Ax \le b,\ x \in \mathbb{Z}^n_{\ge 0}

这里 $c^T x$ 是要最大化的目标值(利润、成本、覆盖率), $Ax \le b$ 把所有资源限制(预算、容量、时间)打包成一个矩阵不等式, $x \in \mathbb{Z}^n_{\ge 0}$ 表示解向量的每个坐标都必须是非负整数。去掉整数条件,就得到下面的线性规划松弛(LP relaxation)。

\max\ c^T x \ \text{s.t.}\ Ax \le b,\ x \in \mathbb{R}^n_{\ge 0}

ILP、LP松弛与分支定界法比较
方法	可行集	复杂度
整数规划	$x \in \mathbb{Z}^n_{\ge 0}$	一般是NP困难的
LP松弛	$x \in \mathbb{R}^n_{\ge 0}$	多项式时间(单纯形法/内点法)
分支定界法	将LP松弛拆分为子问题	最坏情况指数级,实践中通常很快

大学精确保证:最大流最小割定理与分支定界的界

定理: 最大流最小割定理

在任意具有非负边容量、源点 $s$ 和汇点 $t$ 的流网络中,最大 $s$ - $t$ 流的值等于所有 $s$ - $t$ 割中的最小容量。

为什么成立?

该定理把一个最大化问题(求最大流量)转化为一个等价的最小化问题(求最小瓶颈),因此只需给出一个割,就能立刻给出流已经最优的可验证证书——这与支撑LP对偶性和分支定界剪枝的原始-对偶思想相同。

证明

首先证明弱对偶性。取任意 $s$ - $t$ 割 $S$ , $T$ ,其中 $s$ 属于 $S$ , $t$ 属于 $T$ ,以及任意可行流 $|f|$ 。从 $s$ 出发的每一单位流量最终都必须从 $S$ 跨越到 $T$ 才能到达 $t$ ,根据流量守恒,穿过该割的净流量恰好等于流的总值。由于从 $T$ 返回 $S$ 的边只会减少这个净值,流值永远不会超过从 $S$ 出发的边的容量之和,即对任意割都有 $|f|$ 不超过 $\mathrm{cap}(S,T)$ 。

现在将Ford-Fulkerson算法运行至结束:反复在残余图(剩余容量加上已发送流量的可逆部分)中寻找从 $s$ 到 $t$ 的路径,并沿该路径推送该路径上最窄边所允许的最大流量。由于容量假设为整数或有理数,且每次使用路径后沿途容量严格减少,该过程会在有限次增广后终止。

终止时不存在增广路径。设 $S$ 为最终残余图中从 $s$ 可达的节点集合, $T$ 为其余节点(因此 $t$ 属于 $T$ ,因为没有路径能到达它)。原网络中从 $S$ 到 $T$ 的每条边都必须完全饱和(否则它仍有剩余容量,会使 $S$ 进一步扩大),而从 $T$ 返回 $S$ 的每条边流量必须为零(否则其反向残余边会使 $S$ 扩大)。

对 $S$ 中所有节点求和流量守恒可知,总流值恰好等于饱和正向边的容量之和减去为零的反向流量,而这正是该割的 $\mathrm{cap}(S,T)$ 。结合第一段给出的上界,该割达到了可能的最小容量,因此最大流值等于最小割容量。

定理: 分支定界的LP松弛上界

对于最大化整数线性规划,其LP松弛的最优值是整数规划最优值的一个上界;因此,只要某个子问题的LP松弛上界不优于目前找到的最佳整数解,分支定界法就可以舍弃该子问题,而绝不会因此丢失真正的最优解。

为什么成立?

求解LP松弛很快(多项式时间),因此它为目前找到的最佳整数解提供了一个廉价的上界;如果某个分支不可能超过这个上界,继续探索它就是浪费,这正是分支定界法在大规模整数规划上可行的原因。

证明

设 $x \in \mathbb{Z}^n_{\ge 0}$ 为整数可行集, $x \in \mathbb{R}^n_{\ge 0}$ 为同一约束 $Ax \le b$ 下(更大的)LP松弛可行集。由于去掉整数条件只是减少了约束,每个整数可行点也是LP可行的,因此整数可行集是LP松弛可行集的子集。

由于两个问题最大化同一个线性目标函数 $c^T x$ ,且整数规划的可行集包含于LP松弛的可行集之中,在较小集合上能达到的最优值不可能超过在较大集合上能达到的最优值。因此LP松弛的最优值是ILP最优值的一个上界。

分支定界法通过在当前LP松弛解中选取一个取分数值的变量,构造分别添加 $x_1 \le 1$ 或 $x_1 \ge 2$ 的两个子问题来建立搜索树;每个整数可行点恰好满足这两个条件之一,因此这一划分不会丢失任何整数解,反复划分也会持续无遗漏地分割空间。

在每个节点上,求解该子问题的LP松弛,按照上面同样的论证应用于更小的约束集,就得到了该节点之下所有仍可到达的整数解的一个上界。如果这个上界不大于目前在树中任何地方找到的最佳整数解的值,那么该节点的任何后代都不可能改进当前最佳解,因此可以剪掉整个子树,同时仍保证真正的最优解会在树的其他地方被找到。

大学实际应用与典型例题

离散优化支撑着现代世界的物流:航空公司每天求解机组排班的整数规划,芯片制造商用图着色和最大流的思想来布线,配送公司求解的车辆路径问题本质上就是在整数规划上进行分支定界搜索。下面两个例子展示了"LP松弛加分支"和"最大流最小割"这两种模式的实际运用。

例题: 在一个小型ILP上运用分支定界法

在约束 $2x_1 + x_2 \le 5$ 和 $x_1 + 2x_2 \le 5$ 下,最大化 $x_1$ + $x_2$ ,其中 $x_1$ 与 $x_2$ 为非负整数。

解答

第一步:求解LP松弛。两个约束在其交点处最紧:联立求解 $2x_1 + x_2 = 5$ 和 $x_1 + 2x_2 = 5$ 得到 $x_1 = x_2 = \frac{5}{3}$ ,目标函数值为 $\frac{10}{3} \approx 3.33$ 。

第二步:由于LP最优解中的 $x_1$ 是分数,对其分支:一个子问题添加 $x_1 \le 1$ ,另一个添加 $x_1 \ge 2$ 。

第三步:在 $x_1 \le 1$ 这一支上,约束迫使当 $x_1$ = $1$ 时 $x_2$ 最大取到 $2$ ,得到整数点 $x_1 = 1,\ x_2 = 2$ ,对应 $x_1 + x_2 = 3$ 。

第四步:在 $x_1 \ge 2$ 这一支上,约束迫使当 $x_1$ = $2$ 时 $x_2$ 最大取到 $1$ ,得到整数点 $x_1 = 2,\ x_2 = 1$ ,同样对应 $x_1 + x_2 = 3$ 。

第五步:两个分支都已经得到了目标值相同的整数解,因此无需进一步分支;ILP的最优值为 $3$ ,严格小于LP松弛上界 $\frac{10}{3} \approx 3.33$ ,与定理预测一致。

例题: 小型运输网络中的最大流

一个网络包含节点 $s$ , a, b, $t$ ,边的容量为 $s$ →a: $10$ , $s$ →b: $5$ , a→b: $4$ , a→ $t$ : $8$ , b→ $t$ : $9$ 。求从 $s$ 到 $t$ 的最大流。

解答

第一步:沿 $s$ →a→ $t$ 推送流量。瓶颈为 $\min(10,8)=8$ ,因此发送 $8$ 个单位; $s$ →a 这条边还剩 $2$ 个单位容量。

第二步:沿 $s$ →b→ $t$ 推送流量。瓶颈为 $\min(5,9)=5$ ,因此发送 $5$ 个单位;b→ $t$ 这条边还剩 $4$ 个单位。

第三步:利用剩余容量沿 $s$ →a→b→ $t$ 推送流量: $\min(2,4,4)=2$ ,因此再发送 $2$ 个单位。此时从 $s$ 出发的两条边都已用尽。

第四步:发送的总流量为 $8+5+2=15$ 。

第五步:由于从 $s$ 出发的两条边都已饱和,不存在增广路径。仅分离 $s$ 的割的容量为 $10+5=15$ ,与找到的流量一致——根据最大流最小割定理,这确认了 $15$ 是最优的。

如果最大化ILP的LP松弛最优值为 $42.3$ ,关于该ILP的最优值可以得出什么结论?

一家快递公司需要为若干候选路线中的每一条决定是否使用,以在覆盖约束下最小化总成本。哪种建模方式最合适?

在一个流网络中,最小 $s$ - $t$ 割的容量为 $15$ 。最大流的值是多少?

在最大化ILP的分支定界法中,什么时候应该剪掉一个子树?

参考文献

Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan (2021). A (Slightly) Improved Approximation Algorithm for Metric TSP · arXiv:2007.01409