非线性规划中的Benders分解算法基础题

题目描述
考虑一个非线性规划问题，其决策变量可分解为两部分：复杂变量y（如整数或非线性项）和连续变量x，且当y固定时，剩余问题关于x是线性的或易解的。目标是最小化目标函数f(x, y) = cᵀx + dᵀy，约束包括线性约束Ax + By ≥ b（其中A、B为矩阵，b为向量）以及y ∈ Y（Y为离散或复杂约束集）。例如：

• 最小化 f(x, y) = 2x₁ + 3x₂ + y₁ + 4y₂
• 约束：
  x₁ + 2x₂ + y₁ ≥ 5
  3x₁ - x₂ + 2y₂ ≥ 8
  x₁, x₂ ≥ 0
  y₁, y₂ ∈ {0, 1}
  Benders分解通过将原问题分解为主问题（处理y）和子问题（处理x）来求解。

解题过程

1. 问题分解

   • 主问题（Master Problem）：仅包含变量y和辅助变量η，松弛原目标函数中与x相关的部分，初始时无约束（或仅包含y的可行域）。
   • 子问题（Subproblem）：固定y时，求解关于x的线性规划：
     min cᵀx
     s.t. Ax ≥ b - By
     x ≥ 0

2. 迭代步骤

   • 步骤1：求解主问题
     主问题形式：
     min η + dᵀy
     s.t. η ≥ 下界约束（Benders割）
     y ∈ Y
     初始时无Benders割，主问题可能返回一个试探解y*。

   • 步骤2：求解子问题
     固定y = y*，求解子问题：

     • 若子问题可行且有最优解x*，目标值z = cᵀx*。
     • 若子问题无界，需添加可行性割（Feasibility Cut）；若可行，添加最优性割（Optimality Cut）。

   • 步骤3：生成Benders割

     • 最优性割：若子问题可行，设其对偶解为π*（对应约束Ax ≥ b - By），则添加割：
       η ≥ πᵀ(b - By)
       此割确保主问题的η不低于当前y对应的子问题目标值。
     • 可行性割：若子问题无解，通过求解可行性问题（如最小化违反约束的量）得到对偶解σ*，添加割：
       σ*ᵀ(b - By) ≤ 0
       此割排除导致子问题不可行的y。

   • 步骤4：收敛判断
     主问题目标值（η + dᵀy）与当前子问题目标值（z + dᵀy*）的差距小于阈值时停止。否则，返回步骤1。

3. 示例演示
   对上述例题：

   • 初始主问题：min η + y₁ + 4y₂，y₁, y₂ ∈ {0,1}，无割时可能选y*=(0,0)。
   • 子问题：固定y*=(0,0)，求解min 2x₁ + 3x₂，s.t. x₁ + 2x₂ ≥ 5, 3x₁ - x₂ ≥ 8, x≥0。
     子问题可行，最优解x*=(3.2, 0.9)，z=9.1，对偶解π*=(1.4, 0.2)。
     添加最优性割：η ≥ π*ᵀ(b - By) = 1.4×(5 - y₁) + 0.2×(8 - 2y₂) = 8.6 - 1.4y₁ - 0.4y₂。
   • 新主问题：min η + y₁ + 4y₂，s.t. η ≥ 8.6 - 1.4y₁ - 0.4y₂。
     求解得y*=(1,0)，η=7.2，目标值8.2。
   • 重复迭代直至收敛（如y*=(1,1)时子问题目标值12.2，主问题目标值一致，停止）。

4. 关键点

   • Benders割利用对偶理论将子问题信息反馈给主问题。
   • 适用于变量可分离且子问题为线性规划的问题。
   • 收敛性依赖于主问题能不断添加有效割，逐步逼近全局最优解。