这篇博客主要介绍列生成的原理以及应用到VRPTW的实例

基础理论

对偶理论

原理1 每个原始问题的主约束都对应一个对偶变量（dual variable）。该对偶变量的值对应这一主约束不等式右边系数（RHS系数）每增加一个单位，原始问题最优值的变化量。

通常将原始问题的第$i$个主约束的对偶变量记为$v_i$。

原理2 在线性规划的第$i$个约束的对偶变量有以下类型：
| 原始模型 | $i$ 的方向是$\leq$ | $i$ 的方向是$\geq$ | $i$ 的方向是= |
| ————— | ————————— | ————————— | ——————- |
| 最小化目标 | $v_i\leq0$ | $v_i\geq0$ | 无约束 |
| 最大化目标 | $v_i\geq0$ | $v_i\leq 0$ | 无约束 |

原理3 对于最小化线性规划中每个非负变量$x_j$，存在一个相应的主对偶约束$\sum_i a_{i,j}v_i \leq c_j$，限制一个活动的净边际收益不超过既定的成本。在最大化问题中，在$x \geq 0$的情形下，主对偶约束$\sum_i a_{i,j}v_i \geq c_j$限定了梅总活动的净边际成本不少于既定利润。

原理4 如果一个原始线性规划问题有最优解，那么它的最优值与其对偶问题在最优情况下所隐含的所有约束资源的总值相等

原理5 互补松弛定理：如果在原始最优解情况下，一个约束是非积极约束(如果一个不等式在给定解下，不等号左右两边值相等，那么这个不等式是积极约束，反之为非积极约束)，那么它对应的对偶变量$v_i=0$

原理6 如果一个原始变量最优值不为0，那么对应的对偶价格必须使得对应的对偶约束是积极约束；如果对偶价格$v_i$使得对应的对偶约束是非积极约束，那么对应原始变量最优值为0（$x_i=0$）。

原理7 当最小化原始LP问题的变量满足$\boldsymbol{x} \geq 0$条件时，以$\boldsymbol{v}$表示其变量的对偶问题如下：

$$min \quad \boldsymbol{c} \cdot { \boldsymbol{x}} \qquad \qquad min\boldsymbol{b} \cdot \boldsymbol{v} \\ s.t. \quad A\boldsymbol{x} = \left\{\begin{aligned} \leq \\ \geq \\ = \end{aligned}\right\}b \quad s.t. \quad A^T\boldsymbol{v}\geq \boldsymbol{c} \\ \boldsymbol{x}\geq 0 \qquad \qquad \qquad\boldsymbol{v} \left\{\begin{aligned} \leq 0\\ \geq 0 \\ \text{URS} \end{aligned}\right\}$$

其中，对偶变量的符号根据原始问题主约束形式确定

Column generation

Let us call the following liner program the master problem (MP)^[1].

$$z^*_{MP}=min \sum_{j \in J}c_j \lambda_j \\ s.t. \sum_{j \in J} \boldsymbol{a_j} \lambda_j \geq \boldsymbol{b} \\ \lambda _j \geq 0 , \qquad j\in J$$

当$j$增大的时候，主问题的求解难度呈指数增长，因此我们对于MP只考虑求解$J$的子集$J’\subseteq J$ —- the restricted master problem(RMP)，即限制主问题。令$\lambda$和$\pi$分别为RMP的主问题及其对偶问题(跳转对偶理论)的最优解，当$a_j, j \in J$是集合$A$的一个元素，$c_j$可以根据$a_j$通过函数$c$计算得到的时候，则定价子问题（subproblem）为：

$$\overline{c}^*:=min\{c(a)-\pi^ta|a\in A\}$$

如果$\overline{c}^* \geq 0$，即对于任意$j\in J$，其$c_j$非负，则$\lambda$既是RMP的最优解，也是MP的最优解。否则，将求解子问题得到的最优解得到的列加入到RMP中再次进行求解。令$\overline{z}$表示RMP的最优解，当MP最优解的上界$k \geq \sum_{j \in J}\lambda_j$成立时，我们有：

$$\overline{z}+k\overline{c}^* \leq z^*_{MP} \leq \overline{z}$$

dual problem 对偶理论

对偶理论

1. Column generation[M]. Springer Science & Business Media, 2006. ↩