Column-and-constraint generation VS Benders‘ decomposition

论文地址：Solving two-stage robust optimization problems using a column-and-constraint generation method

之前介绍过一个column-and-row generation方法，这次介绍一个更加常用的Column-and-constraint generation（C&CG）。

从论文题目就可以看出，这个方法主要用于two-stage robust optimization (RO) ，也就是robust adjustable or adaptable optimization，也就是说，第二阶段的问题是在第一阶段的决策做出后，对决策进行建模，并根据其不确定性来进行进一步的优化。

但是，这种问题一般很难求解，因为在很多时候，第一阶段的问题甚至都是NP-hard的。有两种思路可以在计算量不大的情况下求解此类问题。

1. 第一种是优化的方法。这种思路假设第二阶段的决策只是一个单纯的函数关系，如仿射函数。
2. 第二种是Benders’ decomposition方法。在第二阶段利用对偶方法基于第一阶段的问题构造一个价值函数value function。所以，这种思路也叫Benders-dual cutting plane algorithms。

而C&CG的思路大致是，在一个确定场景的原始空间动态地生成对于recourse decision variables的约束（dynamically generates constraints with recourse decision variables in the primal space for an identified scenario）。

recourse（追索？不是很确定这个术语是不是这样翻）是RO问题里的一个概念。如果只有一个阶段的RO，自然谈不上追索，也就是problems without recourse。recourse variables可以简单理解为是adjustable decision variables，就是第二阶段里根据不确定性需要去优化和调整的变量。

Two-stage RO问题定义与Benders-dual cutting plane method

考虑第一阶段与第二阶段都是线性优化的情况，同时不确定性是一个有限离散集（finite discrete set）或一个多面体（polyhedron）。

以下是两阶段RO的定义：

其中，是第一个阶段的决策变量，是第二个阶段的决策变量，是不确定集。是由Bender分解定义的cutting plane。

如果代表第二阶段的线性规划问题LP是对任意给定的y和u都可行的，也就是relatively complete recourse的。（这里解释一下这个概念，它是指第二个阶段的问题，对任何第一阶段的决策和不确定集中的任意参数都是可行的。）

那么可以得到它的对偶问题：

这个问题是一个双优化问题（bilinear optimization problem）。可以通过启发式方法或者根据不同特定结构的不确定集解决。

一个切割平面可以直接产生：

将其纳入主问题：

结合SP1我们可以看出，当迭代地引入切割平面和计算MP1时，上界与下界将会不断收敛，最终得到原问题的最优解。

算法的收敛性：

A column-and-constraint generation algorithm

将和都当作是recourse decision variables，原问题可以建模为：

这样，原two-stage RO问题就简化为一个混合整数规划（ mixed-integer program）问题。

基于这样的formulation，很多情况下枚举所有可能的场景是不实际的，比如不确定集特别大的情况。

但是，可以采用部分枚举（partial enumeration）的方法。一是在formulation里看起来比较直接，二是通过添加某些特殊场景的枚举，可以让下界更强。

所以，在C&CG算法中，最重要的一点是去确认和纳入一些重要的场景并产生对应的recourse decision variables。

C&CG的算法流程如下图：

其中，第3步的SP2如下所示：

第4步中的（a）情况对应的是optimality cut，（b）情况对应的是feasibility cut。

算法的收敛性：

与Benders-dual method的对比

1. 主问题中的决策变量个数。C&CG算法通过在每次迭代中引入一组新的变量来增加解空间的维数，而Benders-dual算法一直使用同一组变量。
2. Feasibility cut。C&CG算法提供了处理可行性问题的一般方法，而当前的Benders-dual算法的方法是针对具体问题的。
3. 计算复杂度。与Benders-dual算法相比，C&CG算法求解的主程序变量和约束数量更大。然而，由于在第二阶段极值点的数量相对于变量和约束的数量是指数级的，计算量的减少是非常显著的。仿真结果也可以证明这一点。
4. 解决能力。与Benders-dual算法要求第二阶段问题为LP问题不同，C&CG算法对第二阶段的变量类型没有要求。
5. cut的强度。在相对完整的追索假设下，MP1（来自Benders-dual算法）的最优值是对MP2（来自C&CG算法）最优值的低估。 

拓展

文中还拓展了当不确定集是一般多面体（general polyhedral uncertainty sets）的情况，用到了KKT条件，还有一节是对robust location-transportation问题的case study，感兴趣的话可以找来看看。

另一篇文章Decomposition for adjustable robust linear optimization subject to uncertainty polytope 对此算法做了一定的改进，主要是在松弛其中的relatively complete recourse假设上。

方法评价

• C&CG算法像是一个分解问题的框架，它主张将问题分为主问题MP和子问题SP来解决。而子问题一般是可以用现成的优化工具来解决的。
• 文中对为什么叫column-and-constraint generation没有过多解释，column究竟指的是什么没有特别明确。但是可以猜测应该是指recourse decision variables，而constraint应该是指第4步中生成的与其相关的constraint。
• 文中提到C&CG算法可以轻易地拓展到非线性优化问题中，但未进行进一步解释。
• 文中用到的链接部分已经失效，难以追溯。
• 论文被引用了700+，有一些已经应用此算法解决问题的方案可以参考。