算法背景

Benders分解算法是 J.F.Benders 在1962年首先提出的，旨在解决某些大规模优化问题，其核心思想是将问题划分为多个较小的子优化问题，以取代传统优化方法中同时考虑所有决策变量和所有约束的大规模优化。由于优化问题的计算难度随变量数量和约束数量的增加而显著增加，因此迭代求解多个小规模优化问题往往比解决单个大规模优化问题更有效。

本文只探讨最基础的 Benders 分解算法，只考虑将混合整数规划问题分解为整数规划和线性规划两个子问题。

一、原始优化问题P₁

本文首先讨论最基础的 Benders 解耦问题形式，其优化问题形式如下： 

其中，x与y分别是p维及q维决策向量，Y是多面体，A，B是矩阵，b，c，f是对应维度的列向量，且y是整数型决策变量，x为连续型决策变量。

二、解耦:主问题P₂子问题 P₃

我们将上述优化问题分解为以下两个优化问题：

1）主问题P₂为：

其中，q(y)为以下子优化问题的P₃值（即求解优化问题P₃后，得到c^Tx的值）。

2）子问题P₃为：

显然，P₃在给定y时，是一个线性规划问题。由于该问题的约束条件中耦合了变量  ，故为便于讨论该线性优化问题，我们求其对偶形式。

三、对偶子问题P₄

列出上述优化问题P₃的拉格朗日函数如下：

其中，与为拉格朗日乘子。以x为决策变量极小化拉格朗日函数L，得到以下结果：

因此，可推出下式对偶子问题P₄：

此时，y只存在于对偶子问题的目标函数中，约束条件与y无关，换言之，约束条件形成的多面体与y无关，这么做的好处是，在迭代的过程中，无论 y 取何值，都不会对多面体的形状有任何影响。因此我们下一节才可以针对固定的多面体，讨论其 extreme point 及 extreme rays，不然多面体一直在变，会导致 extreme point 及 extreme rays 也一直在变。

四、讨论

首先，我们先回顾一下基础的对偶理论：

如下图所示，若对偶问题无解（即：对偶问题中的约束条件组成的集合为空集，即：可行集为空集）。此时，原优化问题可能无解，也可能有无界解；若对偶问题存在有界解（即对偶问题中的约束条件组成的集合为非空集，且该对偶问题可求出有界解），则原优化问题也存在有界解；若对偶问题存在无界解（即对偶问题中的约束条件组成的集合为非空集，且对偶问题的解为无界解），则原优化问题无解。该基础结论可总结为下表：

基于上述基础，我们可讨论对偶子问题P₄：

若对偶子问题P₄无解，则子问题P₃无解或无界，这意味着原始优化问题P₁也无解或无界，无意义，不予考虑；

若对偶子问题P₄有解，则存在两种情况，要么是无界解，要么是有界解。

假设可行集（可行域）非空，即对偶子问题P₄有解。不妨设可行集内（即多面体内）存在I个 extreme points 及J个 extreme rays。extreme points 用表述， extreme rays 用表述。其中，extreme points 与 extreme rays 的介绍见本人博客（网址附在文后）。此时，对任意给定的向量，求解对偶子问题P₄后，可得到两种情况：

1.若对偶子问题P₄是无界解：

此时子问题P₃无解，且存在 extreme ray 使得。（这是因为，此时的b-By为常数，而该线性规划问题可行集无界，且优化问题为最大化，因此可以取到正负无穷，则可取到正无穷。此时，对偶子问题P₄是无界解，故原子问题P₃无解，导致原优化P₁也无解）。

2.若对偶子问题P₄是有界解：

此时，可找到一个 extreme point，以最大化目标函数，此时，子问题P₃与 对偶子问题P₄都存在有界最优解。

五、新主问题P₅  

基于上述讨论，我们在主优化问题P₂中新添以下两个约束：

我们将第一个约束称为 Benders feasibility cuts ，我们将第二个约束称为   Benders optimality cuts 。Benders feasibility cuts 旨在排除对偶子问题中无界解的情况（即：排除 extreme ray 的情况），Benders optimality cuts 旨在提高优化问题的性能（即：寻找更好的 extreme point）。此时，主问题P₂可写成下式：

我们称以上优化问题为 RMP（Relaxed Master Problem），即具有部分 cuts 的主问题 。至此，基础的推导已全部完毕，下面将给出 Benders 算法的求解流程。

六、算法流程

如下图所示，算法从求解主问题P₅开始（需要注意的是，在首轮迭代时，不需添加 Benders feasibility cuts 约束及 Benders optimality cuts 约束，只需向主问题P₅中添加q≥0的约束即可），并得到一组解（y*,q*），并将得到的y*代入到对偶子问题P₄中，计算最优的：

1.若得到的无界解（即：该最大化问题中得到最优解时的趋于正负无穷，毕竟是纯线性规划...），则获取该对偶子问题的 extreme ray，并向主问题P₅中添加 Benders feasibility cuts 约束（Benders feasibility cuts 约束其实就是将 extreme ray 中的取值（并非正负无穷了哦，此为 extreme ray 中的取值，而非对偶子问题为最优解时的取值）代入到对偶子问题的目标函数中，并令代入 extreme ray 后的目标函数值小于等于0，便是 Benders feasibility cuts 约束了），并重新计算主问题P₅，即回到流程图中“求解主问题P₅”的那一步；

2.若得到有界解，即有界的，则计算，比较q（y*）与q*，若两者相等，则循环终止，输出最优解即可。若两者不相等，则添加 Benders optimality cuts 约束后，重新计算主问题P₅，继续迭代循环。

收敛性：由于 extreme points 的数量I和 extreme rays 的数量J是有限的，并且在每次迭代中都会生成新的 Benders feasibility cuts 或 Benders optimality cuts，因此该方法通过有限次的迭代后必收敛，且会收敛到最优解。

总结：Benders 解耦法实际上是将整数优化变量留在主问题中，将连续性变量解耦至子问题中，通过两层解耦法，不断迭代，求得混合整数规划问题的最优解。未来我们将更新 Benders 解耦法的 Extensions 部分。 

七、参考网址

[1] Benders Decomposition：
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.717.1297&rep=rep1&type=pdf

[2] 维基百科 Generalized Benders decomposition (GBD)：https://optimization.mccormick.northwestern.edu/index.php/Generalized_Benders_decomposition_%28GBD%29

[3] Paper-Generalized Benders Decomposition：https://www.anderson.ucla.edu/faculty/art.geoffrion/home/docs/GBD.pdf

[4] 我的博客—Extreme Points and Extreme Rays介绍：

https://blog.csdn.net/weixin_43509834/article/details/124594521?spm=1001.2014.3001.5501

---

本文转载自微信公众号：优化与博弈的数学原理

算法背景

Benders分解算法是 J.F.Benders 在1962年首先提出的，旨在解决某些大规模优化问题，其核心思想是将问题划分为多个较小的子优化问题，以取代传统优化方法中同时考虑所有决策变量和所有约束的大规模优化。由于优化问题的计算难度随变量数量和约束数量的增加而显著增加，因此迭代求解多个小规模优化问题往往比解决单个大规模优化问题更有效。

本文只探讨最基础的 Benders 分解算法，只考虑将混合整数规划问题分解为整数规划和线性规划两个子问题。

一、原始优化问题P₁

本文首先讨论最基础的 Benders 解耦问题形式，其优化问题形式如下： 

其中，x与y分别是p维及q维决策向量，Y是多面体，A，B是矩阵，b，c，f是对应维度的列向量，且y是整数型决策变量，x为连续型决策变量。

二、解耦:主问题P₂子问题 P₃

我们将上述优化问题分解为以下两个优化问题：

1）主问题P₂为：

其中，q(y)为以下子优化问题的P₃值（即求解优化问题P₃后，得到c^Tx的值）。

2）子问题P₃为：

显然，P₃在给定y时，是一个线性规划问题。由于该问题的约束条件中耦合了变量  ，故为便于讨论该线性优化问题，我们求其对偶形式。

三、对偶子问题P₄

列出上述优化问题P₃的拉格朗日函数如下：

其中，与为拉格朗日乘子。以x为决策变量极小化拉格朗日函数L，得到以下结果：

因此，可推出下式对偶子问题P₄：

此时，y只存在于对偶子问题的目标函数中，约束条件与y无关，换言之，约束条件形成的多面体与y无关，这么做的好处是，在迭代的过程中，无论 y 取何值，都不会对多面体的形状有任何影响。因此我们下一节才可以针对固定的多面体，讨论其 extreme point 及 extreme rays，不然多面体一直在变，会导致 extreme point 及 extreme rays 也一直在变。

四、讨论

首先，我们先回顾一下基础的对偶理论：

如下图所示，若对偶问题无解（即：对偶问题中的约束条件组成的集合为空集，即：可行集为空集）。此时，原优化问题可能无解，也可能有无界解；若对偶问题存在有界解（即对偶问题中的约束条件组成的集合为非空集，且该对偶问题可求出有界解），则原优化问题也存在有界解；若对偶问题存在无界解（即对偶问题中的约束条件组成的集合为非空集，且对偶问题的解为无界解），则原优化问题无解。该基础结论可总结为下表：

基于上述基础，我们可讨论对偶子问题P₄：

若对偶子问题P₄无解，则子问题P₃无解或无界，这意味着原始优化问题P₁也无解或无界，无意义，不予考虑；

若对偶子问题P₄有解，则存在两种情况，要么是无界解，要么是有界解。

假设可行集（可行域）非空，即对偶子问题P₄有解。不妨设可行集内（即多面体内）存在I个 extreme points 及J个 extreme rays。extreme points 用表述， extreme rays 用表述。其中，extreme points 与 extreme rays 的介绍见本人博客（网址附在文后）。此时，对任意给定的向量，求解对偶子问题P₄后，可得到两种情况：

1.若对偶子问题P₄是无界解：

此时子问题P₃无解，且存在 extreme ray 使得。（这是因为，此时的b-By为常数，而该线性规划问题可行集无界，且优化问题为最大化，因此可以取到正负无穷，则可取到正无穷。此时，对偶子问题P₄是无界解，故原子问题P₃无解，导致原优化P₁也无解）。

2.若对偶子问题P₄是有界解：

此时，可找到一个 extreme point，以最大化目标函数，此时，子问题P₃与 对偶子问题P₄都存在有界最优解。

五、新主问题P₅  

基于上述讨论，我们在主优化问题P₂中新添以下两个约束：

我们将第一个约束称为 Benders feasibility cuts ，我们将第二个约束称为   Benders optimality cuts 。Benders feasibility cuts 旨在排除对偶子问题中无界解的情况（即：排除 extreme ray 的情况），Benders optimality cuts 旨在提高优化问题的性能（即：寻找更好的 extreme point）。此时，主问题P₂可写成下式：

我们称以上优化问题为 RMP（Relaxed Master Problem），即具有部分 cuts 的主问题 。至此，基础的推导已全部完毕，下面将给出 Benders 算法的求解流程。

六、算法流程

如下图所示，算法从求解主问题P₅开始（需要注意的是，在首轮迭代时，不需添加 Benders feasibility cuts 约束及 Benders optimality cuts 约束，只需向主问题P₅中添加q≥0的约束即可），并得到一组解（y*,q*），并将得到的y*代入到对偶子问题P₄中，计算最优的：

1.若得到的无界解（即：该最大化问题中得到最优解时的趋于正负无穷，毕竟是纯线性规划...），则获取该对偶子问题的 extreme ray，并向主问题P₅中添加 Benders feasibility cuts 约束（Benders feasibility cuts 约束其实就是将 extreme ray 中的取值（并非正负无穷了哦，此为 extreme ray 中的取值，而非对偶子问题为最优解时的取值）代入到对偶子问题的目标函数中，并令代入 extreme ray 后的目标函数值小于等于0，便是 Benders feasibility cuts 约束了），并重新计算主问题P₅，即回到流程图中“求解主问题P₅”的那一步；

2.若得到有界解，即有界的，则计算，比较q（y*）与q*，若两者相等，则循环终止，输出最优解即可。若两者不相等，则添加 Benders optimality cuts 约束后，重新计算主问题P₅，继续迭代循环。

收敛性：由于 extreme points 的数量I和 extreme rays 的数量J是有限的，并且在每次迭代中都会生成新的 Benders feasibility cuts 或 Benders optimality cuts，因此该方法通过有限次的迭代后必收敛，且会收敛到最优解。

总结：Benders 解耦法实际上是将整数优化变量留在主问题中，将连续性变量解耦至子问题中，通过两层解耦法，不断迭代，求得混合整数规划问题的最优解。未来我们将更新 Benders 解耦法的 Extensions 部分。 

七、参考网址

[1] Benders Decomposition：
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.717.1297&rep=rep1&type=pdf

[2] 维基百科 Generalized Benders decomposition (GBD)：https://optimization.mccormick.northwestern.edu/index.php/Generalized_Benders_decomposition_%28GBD%29

[3] Paper-Generalized Benders Decomposition：https://www.anderson.ucla.edu/faculty/art.geoffrion/home/docs/GBD.pdf

[4] 我的博客—Extreme Points and Extreme Rays介绍：

https://blog.csdn.net/weixin_43509834/article/details/124594521?spm=1001.2014.3001.5501

---

本文转载自微信公众号：优化与博弈的数学原理