benders分解算法 逻辑思路整理（加星）

Benders decomposition

目录

1.benders的分类

2. 经典的benders分解

2.1 经典的benders分解注意点

2.2 benders分解的核心——子问题和对偶子问题的分析

---

benders分解本质是：
（1）将问题分解为松弛主问题和子问题
（2）子问题不断返回可行割和最优割，然后把这些割添加到松弛主问题中去。

直到子问题提供的上界UB和主问题提供的LB相等，此时得到最优解。（其实此时松弛主问题基本等同于原问题了。）

1.benders的分类

benders目前有三种：
（1）经典的benders分解 Classical Benders 
1960年由benders提出；
主问题是只保留整数变量的松弛主问题，子问题是线性规划问题。

（2）基于整数的benders  Integer-based Benders
1993年由研究VRP的加拿大大佬提出；
子问题不再是线性规划了，因此不能再用对偶线性规划的性质了。
但是仍然可以根据套路（固定公式）添加可行割和最优割。

（3）基于逻辑的benders Logic-based Benders
是最新的，2019年提出的（我不是很确定）？
需要根据问题而定制，不再有固定的公式套用了。

总结一下，前两种是只要符合形式，就可以套用，是通用性框架；而第三种的基于逻辑的benders是定制化方案，不再是通用性框架了。

一般我们经常可以看到的是经典的benders，此处我也结合经典的benders梳理下思路。

2. 经典的benders分解

2.1 经典的benders分解注意点

假设是min问题，y是整数变量，x是实数变量。

再来回顾下benders的主要思路：
（1）将问题分解为master problem松弛主问题（只包含y）和sub problem子问题（只包含x）
（2）主问题给子问题一个的整数解y（此时子问题拿到y以后就变成了一个仅仅包含x的函数），然后子问题返回可行割或最优割，然后把这些割添加到松弛主问题中去。不断循环，直到上下界相等，问题求解结束。

注：

可行割是切除不可行的解；最优割是让解变得更好。

从主要思路里可以看到：

（1）benders是不断添加割的，割就是割平面，也就是不断加约束，也被叫做行生成。利用的原理是，最优解可能不需要全部的约束，可能只需要一部分就可以了。因此我们寻找这些起作用的即可，一个个添加，直到问题求解。

（2）主问题不断给子问题传输整数解y，给了若干次（部分的整数解）就可以求解结束，不必再用枚举的方式枚举所有的整数解。因此本质是部分枚举的方式。

（3）松弛主问题对应的是下界（因为只考虑了部分约束，因此可行域变大，解更好。）而子问题对应的是上界（因为接收的是整数解y，满足整数约束，因此得到的是MIP的可行解，是上界。）

在子问题求解后，更新上界；子问题把割传递给松弛主问题后更新下界（松弛主问题添加割后，即添加了约束，可行域变小，约束得更紧了因此解会变大，即会往上提下界，下界会变大）。

直到上下界相等，问题求解结束，输出最终结果。

2.2 benders分解的核心——子问题和对偶子问题的分析

 原MIP中含有整数变量y，和连续变量x。把整数变量y以及只包含y的相关约束放在松弛主问题里，松弛主问题是一个标准的MIP。子问题中包含连续变量x和常数y，因为y是常数，因此是只包含连续变量x的线性规划LP问题。由于常数y部分，每次松弛主问题给的是不同的常数y，子问题的可行域是不断变化的（Ax≥b-By，常数y是约束右端项是不断变化的）。因此分析子问题不太方便，那么转化为对偶子问题，可行域里没有常数y，跑到目标函数中了。

所以对偶子问题是关键，是benders的核心。

再来梳理下：

（1）子问题和松弛主问题和原问题是一条线；

子问题若无解，那么松弛主问题也无解，原问题也无解；无界也是一样的。

（2）子问题和对偶子问题是一条线。

可以利用对偶的性质。

综上，可以得到下面这张图：

上面这张图是精髓了。一定要理解。

注：需要补充的一点是，当对偶问题无解时，原问题（最开始的初始问题）无解或无界。

（1）无界好说。固定某些变量后对应的子问题无界，那么原问题一定也无界。比如我们固定的是y，即存在y∈Y，使得子问题无界，子问题是其中的一种情形，即包含所有情形的原问题（最开始的问题）无界。

（2）当对偶问题对应的子问题无解时，即存在y∈Y，使得原问题无解。原因是在对偶问题中，y只存在于目标函数项，与约束无关。对偶问题无解，即不存在可行域，那么换了y，仍然不存在可行域，即原问题仍然是无解的。也就是说，只要存在一个y∈Y，使得子问题的对偶问题无解（不可行），那么不论y取别的什么值，子问题的对偶问题依旧不可行。那么子问题不可行，最终得到原问题（最开始的问题）不可行。

下面开始分析具体过程，来帮助我们理解上图最后一列上数学表达是怎样的：

（1）对偶子问题无界，那么一定存在极方向u_r，朝着u_r的方向，函数值达到无界。

因为对偶问题是max问题，也就是说函数值可以达到+无穷，换句话说极方向和梯度的夹角<90°，这样才能达到+无穷。

用数学式子表示是，极方向(u_r)与梯度(b-By)点乘>0，此时对偶子问题无界。

我们想让对偶子问题有界，那么需要反其道而行（逆否命题），也就是要求极方向(u_r)与梯度(b-By)点乘≤0，即u_r*(b-By)≤0。该式即为可行割，几何上上讲就是割去不可行的部分。

（2）对偶子问题有界，有解，那么就能达到唯一最优解u*。

注意，这是在松弛主问题给了一个定值y的情况下达到的最优解u*，是原问题的一个子集。那么对于不同的y，对于对偶子问题max问题而言，可以找到更好的q，也就是q≥(b-By)u*+f*y，也就是找到更好的解。

每次主问题给对偶子问题一个y，对偶子问题进行求解，若无界，则返回可行割；若有界返回最优割，更新上界。将割返回给主问题，求解主问题，得到一个新的y，以及更新下界。不断循环，直到上界=下界时停止。

从约束的角度看，因为不断添加可行割，因此被称为行生成。

从变量的角度看，因为是枚举了一部分y，并非把所有的y传递给x，因此核心是部分枚举的思路。

从主问题和子问题的角度来看，原问题是n1+n2维（y为n1维，x是n2维）的问题；而松弛主问题是n1+1（y为n1维，q为1维）维，子问题及其对偶子问题是n2维的问题。也就是说问题的维度得到降低，求解变得容易了。降维思维的应用。

相关资料：
LBBD
• The Benders decomposition algorithm: A literature review, 2017, Ragheb Rahmaniani,
etc., EJOR
• Logic-Based Benders Decomposition for Large-Scale Optimization, 2019, John N.
Hooker, book chapter.
IBBD
• The integer L-shaped method for stochastic integer programs with complete recourse,
1993, Gibert Laporate and Francois V. Louveaux, Operations Research Letters
• Improving the Integer L-Shaped Method, 2016, Gustavo Angulo, etc., INFORMS Journal
on Computing

运筹优化课程 012-Benders Decomposition

Benders decompositon学习笔记记录_可行割与最优割_云湖在成长的博客-CSDN博客