当前位置: 代码迷 >> 综合 >> Column-and-constraint generation VS Benders‘ decomposition
  详细解决方案

Column-and-constraint generation VS Benders‘ decomposition

热度:54   发布时间:2024-01-13 05:15:26.0

论文地址: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的定义:

其中,y是第一个阶段的决策变量,x是第二个阶段的决策变量,\mathcal{U}是不确定集。是由Bender分解定义的cutting plane。

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

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

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

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

将其纳入主问题:

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

算法的收敛性:

A column-and-constraint generation algorithm

\mathcal{U}x^r都当作是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+,有一些已经应用此算法解决问题的方案可以参考。
  相关解决方案