延续我上一篇文章的主题，我们知道 Asadpour 非对称旅行商问题中的 Held-Karp 松弛不能在实践中写成线性规划的标准矩阵形式。因此，我们需要一种不同的方法来求解松弛，这就是椭球法发挥作用的地方。椭球法可以用来求解半无限线性规划，而这正是 Held-Karp 松弛的类型。
椭球法的一个关键是分离预言机。从算法本身的角度来看，预言机是一个黑盒程序，它接受一个向量并确定
- 该向量是否在线性规划的可行域内。
- 如果不是，则返回一个超平面，该超平面将给定点放在一侧，并将线性规划的可行域放在另一侧。
在最基本的形式中，椭球法是一种决策算法，而不是优化算法，因此它一旦找到可行域内的一个单一（但几乎肯定是非最优的）向量就会终止。然而，我们可以将椭球法转换为一种真正是优化的算法。这对我们来说意味着我们可以假设分离预言机将返回一个超平面。
然后使用预言机返回的超平面来构造算法中的下一个椭球，该椭球具有更小的体积并包含来自原始椭球的一半椭球。然而，这是另一篇文章的主题。现在我只想关注这个“黑盒”分离预言机。
Held-Karp 松弛是半无限的原因是，对于一个具有 $n$ 个顶点的图，程序中存在 $2^n + 2n$ 个约束。分离预言机的一种天真的方法是针对输入向量单独检查每个约束，创建一个运行时间为 $O(2^n)$ 的程序。虽然它最终会终止，但这样做肯定会花费很长时间。
因此，我们寻找一种更有效的方法来做到这一点。回想一下 Asadpour 论文 [1] 中的 Held-Karp 松弛是以下线性规划。
$$ \begin{array}{c l l} \text{min} & \sum_{a} c(a)x_a \\\ \text{s.t.} & x(\delta^+(U)) \geqslant 1 & \forall\ U \subset V \text{ and } U \not= \emptyset \\\ & x(\delta^+(v)) = x(\delta^-(v)) = 1 & \forall\ v \in V \\\ & x_a \geqslant 0 & \forall\ a \end{array} $$
第一组约束确保松弛的输出是连通的。这被称为子游消除，它通过确保每个顶点集至少有一个总的输出弧来防止具有多个不连通集群的解（我们目前正在处理分数弧）。从分离预言机的角度来看，我们并不关心所有满足 $x(\delta^+(U)) \geqslant 1$ 的顶点集，而只试图找到一个这样的顶点子集，其中 $x(\delta^+(U)) < 1$。
为了找到这样一组顶点 $U \in V$，其中 $x(\delta^+(U)) < 1$，我们可以找到对所有 $U \subset V$ 具有最小 $\delta^+(x)$ 值的子集 $U$。也就是说，找到使用分离预言机输入向量给出的边容量的完整有向图中的全局最小割。使用 Michel X. Goemans 的讲义笔记（他也是该项目旨在实现的 Asadpour 算法的作者之一）[2]，我们可以通过 $2(n - 1)$ 次最大流计算来找到这样的最小割。
讲义笔记 [2] 的第 6.4 节中描述的算法相当简单。令 $S$ 为 $V$ 的一个子集，$T$ 为 $V$ 的一个子集，使得 $s-t$ 割是该图的全局最小割。首先，我们在图中选择一个任意的 $s$。根据定义，$s$ 要么在 $S$ 中，要么在 $T$ 中。现在我们遍历图中的所有其他顶点 $t$，并计算 $s-t$ 和 $t-s$ 的最小割。如果 $s \in S$，那么我们会发现 $t$ 的选择之一将产生全局最小割，而 $s \not\in S$ 或 $s \in T$ 的情况可以通过使用 $t-s$ 割来涵盖。
根据 Geoman [2]，使用有效的最大流算法在加权有向图中找到全局最小割的复杂度为 $O(mn^2\log(n^2/m))$。
可以通过一个简单的循环在 $O(n)$ 时间内检查第二个约束。实际上，首先检查这个约束是有意义的，因为它在计算上更简单，因此，如果其中一个条件违反了，我们就可以更快地返回违反的超平面。
现在我们将预言机的复杂度从 $O(2^n)$ 降低到与找到全局最小割相同的 $O(mn^2\log(n^2/m))$，这要好得多。例如，让我们考虑一个具有 100 个顶点的初始图。使用 $O(2^n)$ 方法，也就是说我们需要检查 $1.2677 \times 10^{30}$ 个子集 $U$ 乘以实际确定约束是否违反 $x(\delta^+(U)) \geqslant 1$ 的复杂度。对于同一个具有 100 个顶点的完整有向图，我们知道 $n = 100$，$m = \binom{100}{2} = 4950$。使用全局最小割方法，包括找到最大流以及需要找到的次数的复杂度为 15117042 或 $1.5117 \times 10^7$，比 $10^{23}$ 快。
参考文献#
[1] A. Asadpour, M. X. Goemans, A. Mardry, S. O. Ghran 和 A. Saberi，非对称旅行商问题的 o(log n / log log n) 近似算法，运筹学，65 (2017)，第 1043-1061 页，https://homes.cs.washington.edu/~shayan/atsp.pdf。
[2] M. X. Goemans，关于流和割的讲义笔记，讲义 18，麻省理工学院，剑桥，马萨诸塞州，2009 年 http://www-math.mit.edu/~goemans/18433S09/flowscuts.pdf。