线性规划技巧之行生成

本文介绍的行生成方法，也称为 Benders 分解。我们先看一个问题，然后从这个问题出发，来介绍行生成的思想。

设施选址问题

某物流公司要开设仓库，从而服务周边的客户。仓库有“开仓成本”。仓库与客户之间，存在“连接成本”。

已知 $m$ 个"候选仓库"和 $n$ 个客户。要决定开哪些仓库，从而覆盖所有客户，目标是使得总成本最小。

数学规划

根据问题描述，先定义参数和决策变量。

再描述目标和约束，从而得到它的数学规划。

注意，$x_{i,j}\in\set{0,1}$ 可以放松成 $x_{i,j}\geq 0$，这不会改变原问题的最优解（证明略）。

行生成

如果问题规模不大，可以试着直接求解。如果解不出来，可以把它分解成小问题，然后用迭代的方式，去逼近最优解。

下面介绍如何分解。

注意决策变量，其中 $x_{i,j}$ 是连续变量，$y_i$ 是离散变量。如果固定 $y_i$，那么它变成连续问题，如下所示。

其中 $P_y(x)$ 是线性规划，解起来相对容易。如果把它作为子问题，单独求解行不行？

那么原问题，可以写成这样。

但是，这么做有个麻烦。

子问题的可行域，依赖主问题的 $y$ 值。而主问题的可行域，也依赖子问题的 $x$ 值。两者互相依赖，子问题就不好拆。

下面换个思路。考虑 $P_y(x)$ 的对偶问题。

注意 $y$ 的位置，从约束变成了目标。换句话说，对偶问题的可行域，不受 $y$ 值的影响。

再看原问题，它变成了这样。

引入中间变量 $z$，写成如下形式。

看这个形式，似乎更复杂了。约束数量等于 $|I|$。换句话说，约束有无数多个。这更难计算了。

但是，它有个好处。哪怕只考虑一部分约束，它的解始终是原问题的可行解（因为 $\alpha,\beta$ 可行）。换句话说，计算的时候，可以只考虑一部分约束，先求得可行解。然后用迭代的方式，逐步逼近最优解。

这样一来，主问题的约束，可以逐个增加。通过求解子问题 $D_y(\alpha,\beta)$ ，得到可行的 $\alpha,\beta$ 值，也是主问题的约束。每迭代一轮，主问题增加一行，这就是 Benders 分解，也称为行生成方法。

迭代过程

下面介绍具体的迭代过程。

第一步，初始化，令 $z=0$，$I=\emptyset$。

主问题的形式如下：

第二步，求解主问题，得到 $y^*, z^*$。

注意到，主问题考虑的约束，是原问题约束的子集。因此，其最优目标函数值，是“原问题”的最优目标函数值 $\text{OPT}$ 的下界，即

第三步，求解子问题 $D_{y^*}(\alpha,\beta)$，得到 $\alpha^*, \beta^*$。

接着，主问题新增一行，即 $I=I\cup {(\alpha^*, \beta^*)}$。

令 $\text{OPT}_S$ 为子问题的最优目标函数值。回顾原问题的等价形式 $P_1(y,\alpha,\beta)$ 和 $P_2(y, z)$ ，我们有

从而得到 $\text{OPT}$ 的上界，即

第四步，判断停止条件。给定 $\epsilon >0$， 比如 $\epsilon=1e-6$，当 $\text{ub}-\text{lb} < \epsilon$ 时，停止；否则执行第二步。

以上就是行生成方法的迭代过程。

但是，没有完。按上述步骤，其实解不出来。会出现子问题无解，从而无法迭代。所以需要打个补丁，下面讲怎么打。

可行性

要顺利迭代，就要保证子问题 $D(\alpha,\beta)$ 有可行解。而 $D(\alpha,\beta)$ 是 $P_y(x)$ 的对偶问题，所以 $P_y(x)$ 要有可行解。

换句话说，给定任意的 $y$，存在 $x$ 使得下面的约束成立。

容易发现，当 $y=0$ 时 $x=0$，等式不能满足，此时 $P_y(x)$ 无可行解。

我们理解一下，当 $y=0$ 时， 意味着不开仓。而上面的等式，要求所有客户被连接。不开仓就连接不了客户，所以不可行。

为了连接所有客户，至少要开一个仓。即 $$ \sum_{i=1}^m y_i \geq 1. $$

那么主问题，应该是这样。

这样一来，它解出来的 $y$ 值，使得子问题可行。也就是说，上面的迭代过程，能顺利执行。

最后，还有个小问题。

主问题解的是 $y,z$，子问题解的是 $\alpha,\beta$ ，而原问题解的是 $x,y$ 。已知主问题和子问题的解，怎么得到原问题的解？

回顾子问题 $D_y(\alpha,\beta)$ ，它的对偶问题是 $P_y(x)$ 。换句话说，已知 $\alpha,\beta$ ，它的对偶变量就是 $x$。利用求解器（比如OR-tools），可直接返回 $\alpha,\beta$ 的对偶变量值 $x$。

总结

列生成方法，适合求解这种形式的规划：

其中与 $y$ 相关的部分，可以是非线性的。给定 $y$ ，关于 $x$ 的问题，就是线性规划。考虑它的对偶，从而把与 $y$ 相关的部分，从约束转移到目标。这样一来，原问题的约束，来自对偶问题的解。

那么原问题就可以拆成两个问题：一个是原问题的目标，作为主问题，另一个是原问题的约束，来自对偶问题，作为子问题。交替求解主问题和子问题，从而逼近原问题的最优解。

值得注意的是，要保证迭代是可行的，就要保证子问题可行。一般来说，只要问题本身合理，可行性就容易满足。但是可能存在，主问题的某些 $y$ 值导致子问题不可行。添加相应的约束，可以避免这种情况的发生。