问题定义

对于一个存在耦合约束或复杂变量的较难优化问题：

\begin{gather*} min \, c^Tx+f^Ty \\ s.t \, Ax+By = b \\ x \in X \\ x \geq 0 \\ y \in Y \end{gather*}

假设 $y$ 是整数或BINARY等复杂变量，当 $y$ 值固定时，原问题可以转化为相对容易求解的问题，故该问题可以拆分为==主问题==和==子问题==两部分：

\begin{gather*} min \, f^Ty + q(y) \\ \tag{Master} y \in Y \end{gather*}

\begin{gather*} min \, c^Tx\\ s.t \, Ax = b - By \\ x \in X \\ \tag{Sub} x \geq 0 \end{gather*}

由于Sub子问题的可行域受Master主问题中设定的 $y$ 取值影响，不好定量判断是否为空集，故将子问题写成对偶问题形式

\begin{gather*} max \, u^T(b-By) \\ s.t \, A^Tu \leq c \\ \tag{Sub-Dual} u 无约束 \end{gather*}

若Sub-Dual问题可行域为空（注意这里的可行域与 $y$ 无关，下述内容对Master主问题中 $\forall y \in Y$ 成立），即子问题的对偶问题不可行，则子问题无界或不可行，此时对 $\forall y \in Y$ ，整个问题都不可解，我们不考虑这种情况，只考虑Sub-Dual子问题可行域不为空的情况，设此时该子问题的极点和极射线集合如下：极点和极射线

\begin{gather*} \{u_{p}^{i} | \forall i \in I\}：极点集合 \\ \{u_{r}^{j} | \forall j \in J\}：极射线集合 \end{gather*}

极点和极射线对问题的性质影响如下：

若存在某条极射线使得

\begin{aligned} (u_{r}^{j})^T(b-By)>0 \end{aligned}

则Sub-Dual无界 2. 若存在某个极点使对偶目标函数值最大

\begin{aligned} (u_{p}^{i})^T(b-By) = max\{(u_{p}^{i})^T(b-By) | \forall \, i \in I\} \end{aligned}

则Sub子问题有有限的最优解

综上，Sub-Dual可以写成：

\begin{gather*} min \, q \\ s.t\,(u_{r}^{j})^T(b-By)\leq0 \\ (u_{p}^{i})^T(b-By)\leq q \\ \tag{Sub-Dual} q无约束 \end{gather*}

Sub-Dual改写完毕后，可将其代回到Master主问题中

\begin{gather*} & min \, f^Ty + q \\ s.t\, &(u_{r}^{j})^T(b-By)\leq0 \\ &(u_{p}^{i})^T(b-By)\leq q \\ \tag{master} & y \in Y \\ & q无约束 \end{gather*}

\begin{gather*} &(u_{r}^{j})^T(b-By)\leq0 \tag{1} \end{gather*}

\begin{gather*} &(u_{p}^{i})^T(b-By)\leq q \tag{2} \end{gather*}

此时，表面看上去问题转化成了一个仅有 $y$ 的优化问题，但实际上，列出全部的极点和极射线基本是不可能的。因此，我们下面介绍Benders分解法的具体步骤

Benders算法步骤

不添加任何约束簇（1）和约束簇（2）中的约束，求解Master问题，得到原问题的 $LB$ ：此时Master问题中目标函数和约束中都不考虑x的影响，约束比原问题少很多，目标函数中除 $y$ 之外的 $q$ 也无约束，因此其必然是原问题的一个下界
第1步得出的 $y$ $y$ 传到Sub中（实际操作中为了方便可以不将子问题转化为Sub-Dual的对偶形式），求解Sub子问题：
1. 如果Sub子问题可行，那么此时这组（ $x$ , $y$ ）为可行解，此时子问题的目标函数值与主问题的目标函数值之和必然为原问题的上界。因此，从子问题中得到极点（对偶问题最优解 $\pi$ ），更新原问题的上界 $UB$ ，并添加最优约束cut(2)
2. 如果Sub子问题不可行，则得到极射线，添加可行约束cut(1)（这里要注意，如果子问题不转化为其对偶形式，基于Gurobi直接获取Constr.FarkasDual属性作为极射线的话，需要对该属性取负值才是真正的极射线向量值）
接着求解Master问题，得到 $y$ 值返回给子问题，直到 $UB$ 和 $LB$ 之间的 $gap$ 满足收敛条件为止