在线性规划中，我们有时需要将整数规划“松弛”，或解绑变量的值，使其成为连续值。此过程的一个特定应用是 Held-Karp 松弛，它用于非对称旅行商问题的 Asadpour 算法的第一部分，其中我们找到近似的下界。通常，松弛写成如下形式。
$$ \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} $$
这是一种书写程序的便捷方式，但如果我们想求解它（我们肯定想），则需要将其写成线性程序的标准形式。标准形式使用约束集的矩阵和目标函数的向量表示。如下所示
$$ \begin{array}{c l} \text{min} & Z = c^TX \\\ \text{s.t.} & AX = b \\\ & X \geqslant 0 \end{array} $$
其中 $c$ 是目标函数的系数向量，$X$ 是所有变量值的向量，$A$ 是约束的系数矩阵，$b$ 是约束等于的值的向量。一旦线性程序采用这种形式，就存在可以有效解决它的算法。
在 Held-Karp 松弛中，目标函数是一个求和，因此我们可以将其扩展为求和。如果有 $n$ 条边，则它变为
$$ \sum_{a} c(a)x_a = c(1)x_1 + c(2)x_2 + c(3)x_3 + \dots + c(n)_n $$
其中 $c(a)$ 是图中该边的权重。由此，可以轻松地将目标函数转换为满足标准形式的两个向量。
$$ \begin{array}{rCl} c &=& \begin{bmatrix} c_1 & c_2 & c_3 & \dots & c_n \end{bmatrix}^T \\\ X &=& \begin{bmatrix} x_1 & x_2 & x_3 & \dots & x_n \end{bmatrix}^T \end{array} $$
现在我们必须将约束转换为标准形式。首先，请注意 Held-Karp 松弛包含 $x_a \geqslant 0\ \forall\ a$，而标准形式使用 $X \geqslant 0$，因此这些常数已经匹配，无需任何工作。至于其他的……它们确实需要一些工作。
从 Held-Karp 松弛中的第一个约束开始，$x(\delta^+(U)) \geqslant 1\ \forall\ U \subset V$ 且 $U \not= \emptyset$。此约束指定对于顶点集 $V$ 的每个子集，该子集必须至少有一条弧，其尾部在 $U$ 中，头部不在 $U$ 中。对于任何给定的 $\delta^+(U)$（在论文中定义为 $\delta^+(U) = {a = (u, v) \in A: u \in U, v \not\in U}$，其中此集合中的 $A$ 是图中所有弧的集合），不在 $U$ 中的弧的系数为零。$\delta^+(U)$ 中的弧的系数为 1，因为它们的全部权重被计为 $\delta^+(U)$ 的一部分。我们知道顶点 $V$ 约有 $2^{|V|}$ 个子集，因此此约束为此约束矩阵 $A$ 添加了相同数量的行。
转向下一个约束，$x(\delta^+(v)) = x(\delta^-(v)) = 1$，我们首先需要将其分成两部分。
$$ \begin{array}{rCl} x(\delta^+(v)) &=& 1 \\\ x(\delta^-(v)) &=& 1 \end{array} $$
与最后一个约束类似，这些约束都表示图中进入和离开顶点的弧数需要等于 1。对于每个顶点 $v$，我们找到所有从 $v$ 开始的弧，这些弧是 $\delta^+(v)$ 的成员，因此它们的权重为 1，所有其他弧的权重为零。$\delta^-(v)$ 的情况相反，每个头部在 $v$ 上的顶点都有权重或系数 1，而其余顶点的权重为零。这为系数矩阵 $A$ 添加了 $2 \times |V|$ 行，使总数达到 $2^{|V|} + 2|V|$ 行。
A 的不可能的大小#
我们已经知道 $A$ 将有 $2^{|V|} + 2|V|$ 行。但是 $A$ 将有多少列？我们知道每条弧都是一个变量，因此至少有 $|E|$ 行，但在线性程序的传统矩阵形式中，我们必须引入松弛变量和剩余变量，以便 $AX = b$ 而不是 $AX \geqslant b$ 或任何其他不等式运算。$2|V|$ 行已经符合此要求，但使用 $V$ 的每个子集创建的行没有，这些行仅要求 $x(\delta^+(U)) \geqslant 1$，因此我们为这些行中的每一个引入一个剩余变量，使列数达到 $|E| + 2^{|V|}$。
现在，Asadpour 算法中执行的 Held-Karp 松弛是在完整的双向图上完成的。对于一个有 $n$ 个顶点的图，图中将有 $2 \times \binom{n}{2}$ 条弧。然后，$A$ 大小的更新值为
$$ \left(2^n + 2n \right)\times \left(2\binom{n}{2} + 2^n\right) $$
矩阵。这非常大。对于 $n = 100$，矩阵中有 $1.606 \times 10^{60}$ 个元素。每个条目分配区区 8 位仍然会消耗超过 $1.28 \times 10^{52}$ GB 的内存。
对于任何我们可以运行 NetworkX 的计算机来说，这都是不可能的内存量。
解决方案#
Asadpour 非对称旅行商问题算法必须求解 Held-Karp 松弛，但显然将其转换为标准形式是不可能的。这意味着我们将无法使用我原本希望使用的 SciPy 的 linprog 方法。我将不得不研究并编写一个椭球方法求解器，希望它能够在多项式时间和实际内存量内求解 Held-Karp 松弛。