Benders分解及其python实现
本文的思路和代码部分参考了这篇知乎专栏：【整数规划(九)】Benders 分解（理论分析+Python代码实现） - 知乎 (zhihu.com): https://zhuanlan.zhihu.com/p/428706477。本文对思路和代码进行了改进，添加了自己对理论的理解，同时修改代码，删改了一些我认为不必要的变量，并使得y由实数域扩展到n维实数空间。
benders分解的出发点及原理说明
考虑如下的规划问题：
在求解此问题时，y作为一个整数变量是不好处理的（实际上，Y可以是任何“难以处理的变量”）。如果我们能够”消掉“y而保留x，那么这个问题就变成了一个线性规划问题，我们可以用单纯形法去求解。自然而然地，我们有了这么一个想法：我们先固定一组y，此时问题变为一个关于x的线性规划问题；求解这个线性规划问题，我们可以获得对应于这组y的最优解；然后我们遍历所有可能的y，找到最优解最大的那组y，就能获得全局最优解。
基于上述讨论，我们可以将问题（1）-（3）分解为两个优化问题：
有了上述的优化模型，我们就可以实现我们之前的想法：固定y求解x，再遍历所有的y，最终找到全局最优点。然而这个想法有一个严重的问题：当y的可行域非常大的时候，我们想要遍历y是不现实的。
那么有没有一种方法可以让我们只遍历少数y就能找到最优解呢？实际上，我们可以发现两个事实，它们可以减少我们需要遍历的y的数量：
很多y会使得问题（5）无解，对于这样使问题无解的y，我们是不用遍历的。
在遍历过程中，我们可以记录当前遍历过程中已经找的使W最大的y；对于那些必然不可能获得更大W的y，我们是不用遍历的。
那么，我们怎样才能基于上述想法，排除掉这些不需要遍历的y呢？我们只需要取问题（5）的对偶问题即可。问题（6）是问题（5）的对偶问题。由于问题（5）是一个线性规划问题，根据对偶理论，对偶问题（6）的最优解等于原问题（5）的最优解；同时，问题（6）的解为负无穷，则问题（5）不可行。
我们希望找到使得问题（5）无解的y，也就是找到那些使得问题（6）的解为负无穷的y。为什么要做这个转换呢？因为问题（6）具备一个优良的性质：它的可行域是与y无关的，y仅出现在目标函数值中。对线性规划有了解的同学或许知道，任何一个线性规划的可行解都可以表示为可行域的极点和极射线的线性组合。为了防止大家不熟悉什么是极点和极射线，下面举一个简单的例子：
在上面这个图中，假设紫色区域是可行域，则红色线就是可行域的极射线（无限延伸的射线），绿色的点就是可行域的极点（顶点）；可行域内任何一个点沿着极射线方向无限延伸后仍然处于可行域内。
显然，如果我们希望问题（6）的解不是负无穷，就要求对于可行域内的任意一点沿着任意极射线方向延伸，其目标函数值都不会降低；否则只要无限延伸，就能趋近于负无穷。从数学的语言上来说，假设极射线的的方向向量为v，问题（6）的解不是负无穷的充要条件为：其中N表示极射线的数目。根据式（7），假如我们知道问题（6）可行域中所有极射线的方向，那么对于任意的y，我们不用去求解问题（6）就能知道它会不会趋近于负无穷，也就知道了问题（5）可不可行。如果我们把式（7）对应的约束加到问题（4）中，那么就可以排除掉相当大一部分的y，极大地减少计算量。将问题（5）转换为问题（6）给我们带来的好处还不止上面这些。学过线性规划的同学们肯定知道，根据线性规划的基本定理，若问题（6）有解且非无穷大，则解必然出现在可行域的极点上（也就是多面体的顶点上，上图的绿色点上）。也就是说，如果我们给定一个y并且求解问题（6），得到的最优解u*必然是可行域的一个顶点。我们假设多面体极点的集合为：
由于问题（6）有解且非无穷大时解必然出现在可行域的极点上，因此优化问题（6）等价于如下问题（其思想是遍历所有极点，找到目标函数值最小的那个极点）：
极小化函数等价于最大化函数的下界，我们设函数的下界为η，于是问题（8）可以进一步等价为：
我们把式（9）中φ(y)的表达式带入到式（4）中：
问题（10）是连续求两个最大值，所以中间的括号可以拆开。我们拆掉括号，整理得：
基于之前的讨论，我们把式（7）加入到（11）中，保证问题存在可行解：
理论上来说，我们只要解上面这个整数规划问题，就能获得问题的最优解。
值得注意的是，问题（12）中间“两项”限制条件远远不止两条——实际上，当u的维数p很高的时候，它的可行域的极点与极射线可能会非常非常多（它们的数量会呈现指数级上升，这是很容易想象的），所以我们在求解问题的时候不可能一口气把所有限制条件都加进去，而是要在求解的过程中不断添加——实际上，每给定一组y，求解问题（6)，我们得到的u或者是可行域的极点，或者是可行域的极射线（这里解不作证明了）；我们只要把对应的u或者v带入到（12）中，就能添加一个限制条件，减少y的可行域。
有同学可能会好奇，既然极点和极射线非常多，而我们求解一次只能添加一条极射线或者极点，会不会效率很低？经验表明，很多时候我们只要添加少量的限制条件，就能极大地减少y的可行域，并轻易地找到最优解，所以这个方法是足够有效的。
Benders算法的流程
Step 1:初始化 ，初始化上界UB=+∞，下界LB=-∞。
Step 2: 若UB-LB=δ（提前给定的算法精度），则进入下一步，否则直接输出最优解
Step 3: 求解对偶问题（6），得到最优解 u*
Step 4: 若u*是无穷大，说明u*是极射线的方向。根据式（7)，添加约束到主问题(12)中
Step 5: 若u*不是无穷大，说明u*是极点。根据式（11)，添加约束到问题（12）中，并更新
。（LB记录了到目前为止我们找到的最优的解）
Step 6: 求解主问题（12）得到最优解 y*，η*，然后更新（因为此时主问题（12）中的约束还没有全部被找到，所以这个解不一定是可行的，但是一定大于等于所有约束都被添加进去以后再被求解出的最优解，因此它是真实最优值的上界）
Step 7: 返回step2
总结与拓展（基于逻辑的Benders分解算法）
回顾我们上述的讨论，我们可以发现，Benders分解算法的核心思想就是我们在开始时提出的两个想法：
很多y会使得问题无解——我们利用原问题无解的充要条件，使用对偶问题的极射线添加约束。
我们已经遍历过的点为问题的最优解提供了一个下界——我们使用对偶问题的极点添加约束。
综上所述，我们的目标就是通过添加约束的方式不断缩小y的可行域，并不断更新原问题的上下界。
在很多现实的优化问题中，我们可以利用实际问题的独特特征，来添加约束，从而达到更快地缩小y可行域的目的。这个方法被称为基于逻辑的Benders分解。
对基于逻辑的Benders分解算法以及其他Benders分解算法感兴趣的同学，可以参考这篇综述文章：Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, Walter Rei, The Benders decomposition algorithm: A literature review
