Benders分解如何成？

参考视频：068-线性规划（十三）：Benders分解-哔哩哔哩 1. Benders分解简介 1.1 什么是Benders分解 Benders分解算法是由提出它的Jacobus Franciscus (Jacques) Benders教授的名字命名的，核心思想是将两类变量（一类为整数变量，另一类为连续变量）分开求解，然后再合起来。 举个例子，这就像小鸡炖蘑菇： 传统的做法是把小鸡和蘑菇一锅炖出来。事实上，小鸡比较难炖，蘑菇比较好炖。考虑到这一点，Benders分解的思想就是把小鸡（复杂变量）和蘑菇（简单变量）分开炖，但这两锅又要有联系：因为蘑菇要用鸡汤来炖，在炖的过程中我们又要尝尝蘑菇鸡汤的咸淡，再决定要不要往鸡汤里放更多的盐。也就是说，炖鸡的那口锅要给炖蘑菇的那口锅提供鸡汤，而炖蘑菇的那口锅要给炖鸡的那口锅反馈咸淡。重复上面的过程，直到分开炖的口味和一锅炖出来的口味相差无几，我们就把两口锅的东西合起来，就得到了跟传统做法一样原汁原味的小鸡炖蘑菇(๑´ڡ`๑) 1.2 学习Benders分解的前置知识 Cutting plane（割平面） Vaild inequalities（有效不等式）：也就是割平面的过程中，利用有效不等式，割去一部分内容物，但没有割去最优解（保持最优特性） Row generation（行生成）：行生成的概念 Duality theory（对偶理论）：最核心的知识，详情请见之前的博客大规模线性规划的对偶 - 码头牛牛 - 博客园 首先来介绍一下Benders分解的初步逻辑： 如图，Benders分解会把一个优化问题分解为一个主问题(Master Problem)和一个子问题(Sub-Problem)分别进行求解。 Master Problem (MP)：只剩下复杂变量（在图中指的是整数变量\(y\)）和用来传递信息的变量（在图中指的是变量\(q\)）的优化问题 Sub-Problem (SP)：包含简单变量的优化问题（图中指的是连续变量\(x\)） 在求解过程，MP会先指定一个可行的\(y\)（相当于控制变量），传给SP。 SP会反馈给MP这个\(y\)是否合适。如果合适的话会利用\(y\)的信息帮助找到最优解；如果\(y\)提供的信息无效或者说是不可行的，那就要避免MP下次还提供这样的信息，也就是把这样的信息cut掉。也就是： 然后再简单介绍一下行生成（有关列生成内容在这里：列生成算法 - 码头牛牛 - 博客园）： 行生成关注的是约束，因为约束是以行的形式存在的；列生成关注的是基，因为基是以列的形式存在的。 行生成是从一个隐藏的空间里，不断地去拿有效的约束（有效不等式），并把它们放到松弛的MP里；列生成是从对偶子问题里面，把一个reduce cost比较好的基反馈给MP。 比较典型的行生成方法有：割平面、User Cut等等，下面介绍其中两个： User cut：就是一个提前加的割，作用是减小搜寻范围。在我们对问题有初步把握的基础上，我们可以人工加入几个割平面 (User cut)，来割掉一些多余的搜寻空间，以加速搜索进程 Lazy cut：当需要的时候就添加，不需要的时候就不添加。作用是使解变得更加可行。它的思想和Benders分解中加cut的思想是一致的。 如下面第一张图，黄色部分是松弛后的可行域。当我们比较了解这个问题的时候，就可以事先加入User Cut，来缩小这个黄色的搜寻范围；如下面第二张图，有些问题为了方便求解，需要把一些约束给拿掉，拿掉约束后，它会添加一些不可行的点进来，也就是图中灰色的点。这导致了求解的过程中可能会碰到这些点，如果碰到了发现不可行，我们就会添加一个Lazy Cut进来，把这个点砍掉。所以说Lazy cut就是使用到的时候才会拿出来用，而Benders分解的思想就是不断地向松弛主问题添加Lazy Cut。 2. Decomposition process 如图，给出一个具有两类变量的问题，\(x\)是简单的连续变量，\(y\)是复杂变量，\(y\)的可行域是\(Y\)。然后我们把它分解成两类问题（图中红色的\(y\)是一个变量，绿色的\(y\)是一个给定的值）： SP：只包含\(x\)，在子问题中\(y\)是需要提前给定的。图中SP的目标函数中，\(f^Ty\)其实加不加都行，因为这是个给定常数。 MP：包含变量\(y\)的主问题，它只含有复杂变量。 求解MP，为SP提供一个确定的\(y\)；SP会得到当前\(y\)的求解情况，并以割平面(Cutting plane) 的方式反馈给MP。