Benders分解 第一步：基本概念与问题背景 Benders分解是一种处理大规模混合整数规划（MIP）的算法，由Jacques F. Benders于1962年提出。其核心思想是将原问题分解为两部分： 主问题 ：包含整数变量，负责寻优。 子问题 ：包含连续变量，对给定的整数解进行可行性或最优性检验。 关键动机 ：当问题中连续变量与整数变量耦合时，直接求解计算成本高。通过分解，主问题通过不断添加“割平面”（Benders割）来逼近子问题的信息，从而逐步逼近全局最优解。 第二步：标准问题形式 考虑如下混合整数规划问题： \[ \min_ {x,y} c^T x + d^T y \] \[ \text{s.t. } Ax + By \geq b, \quad x \in X, \ y \geq 0 \] 其中 \(x\) 为整数变量（通常二值或整数约束），\(y\) 为连续变量。Benders分解将该问题重写为： \[ \min_ {x \in X} \left[ c^T x + \min_ {y \geq 0} \{ d^T y \mid By \geq b - Ax \} \right ] \] 内部的最小化问题即为子问题，其最优值依赖于主问题的整数解 \(x\)。 第三步：子问题的处理与对偶转化 对子问题 \(\min_ {y \geq 0} \{ d^T y \mid By \geq b - Ax \}\)，引入对偶变量 \(\lambda \geq 0\)，得到对偶子问题： \[ \max_ {\lambda \geq 0} \{ (b - Ax)^T \lambda \mid B^T \lambda \leq d \} \] 重要性 ： 对偶问题的可行域 \(\{\lambda \geq 0 \mid B^T \lambda \leq d\}\) 是固定多面体，与 \(x\) 无关。 通过强对偶定理，子问题的最优值等于对偶问题的最优值（若子问题可行且有界）。 第四步：Benders割的生成 根据对偶子问题的解，生成两类割平面： 可行性割 ：若对偶问题无界（即子问题不可行），则存在极方向 \(r\) 满足 \((b - Ax)^T r > 0\)，添加割 \((b - Ax)^T r \leq 0\) 到主问题，排除不可行解。 最优性割 ：若对偶问题有最优解 \(\lambda^ \)，则添加割 \(z \geq c^T x + (b - Ax)^T \lambda^ \)，其中 \(z\) 是主问题中代表目标函数下界的辅助变量。 第五步：算法流程 初始化 ：主问题仅包含整数约束和宽松的目标下界。 迭代步骤 ： 求解主问题，得到整数解 \(x^* \)。 求解子问题（或其对偶），生成割平面。 若子问题不可行，添加可行性割；否则添加最优性割。 终止条件 ：当主问题的目标值 \(z\) 与当前子问题目标值之差小于容忍误差时停止。 第六步：应用与扩展 典型场景 ：设施选址、网络规划、随机规划（如两阶段问题）。 改进方向 ： 多割生成（并行求解多个场景）。 Pareto最优割加速收敛。 集成到分支定价框架中（如分支定价割平面法）。 优势 ：通过分解降低问题维度，尤其适用于子问题具有特殊结构（如线性或凸优化）的情况。