本德斯分解

本德斯分解（Benders decomposition）把带有两层决策结构的优化问题分开求解：主问题暂时决定一小组关键变量，子问题在这个决定下计算后续最小费用，再把子问题给出的有效不等式送回主问题。主问题由此逐步学到后续费用的形状，而不必一开始把全部后续变量都装进去。经典形式以连续线性规划作子问题，因此可以利用线性规划对偶给出严格的界。^[1]

一家工厂须交付四件产品。变量 $y \in {0, 1}$ 决定是否开机，开机固定费用三元；正常生产 $x_{1}$ 每件一元，但不超过 $5 y$ 件；应急外购 $x_{2}$ 每件四元，无数量上限。数量在此视为连续可分的教学模型。原问题为 $\begin{matrix} min & 3 y + x_{1} + 4 x_{2}, \\ x_{1} + x_{2} \geq 4, 0 \leq x_{1} \leq 5 y, \\ x_{2} \geq 0, y \in {0, 1} . \end{matrix}$ 不开机只能外购四件，费用十六元；开机生产四件，费用七元。本例容易直接算完，适合完整检查分解所产生的每一道界。

子问题及其费用下界

给定 $y$ ，记正常生产与外购的最小费用为 $Q (y)$ 。给需求约束配非负乘子 $α$ ，给容量上限配非负乘子 $β$ 。对任何子问题可行解，若 $α - β \leq 1, α \leq 4, α, β \geq 0,$ 则 $\begin{matrix} x_{1} + 4 x_{2} & \geq (α - β) x_{1} + α x_{2} \\ = α (x_{1} + x_{2}) - β x_{1} \\ \geq 4 α - 5 y β . \end{matrix}$ 最后一行同时使用需求下限和容量上限。右端由此是所有后续可行方案的下界，且对每个允许的 $y$ 都成立；这正是割的有效性证明。

取乘子 $(α, β) = (4, 3)$ 得 $Q (y) \geq 16 - 15 y$ ，取 $(1, 0)$ 得 $Q (y) \geq 4$ 。若把 $y$ 暂扩展到区间 $[0, 1]$ ，直接生产尽可能多的便宜产品可得 $\begin{matrix} x_{1} & = min (4, 5 y), \\ x_{2} & = max (4 - 5 y, 0), \\ Q (y) & = max (16 - 15 y, 4) . \end{matrix}$ 这组原始可行解达到上面两个下界的较大者，因而证实它确为最优值。虽然主变量只允许零和一，连续图仍能说明两条割分别描述费用函数的哪一段。

补救费用是16减15y与常数4的最大值，两条有效割拼成完整费用下边界 — 绿色折线为真实后续费用；虚线单独看都可能低估，但两者合起来恰好给出本例的费用函数。

三轮主问题计算

在主问题中用变量 $η$ 代表尚未完全认识的后续费用，最初只要求 $η \geq 0$ ，目标为 $min (3 y + η)$ 。这是原问题的松弛，所以其最优值是全局下界；把主问题选出的 $y$ 放回子问题完成生产，则得到可行方案和全局上界。

轮次	已有费用割	主问题选择	下界	子问题给出的可行总费用
1	$η \geq 0$	$y = 0, η = 0$	0	16
2	再加 $η \geq 16 - 15 y$	$y = 1, η = 1$	4	7
3	再加 $η \geq 4$	$y = 1, η = 4$	7	7

第二轮的四元不是实际开机费用，而是主问题尚在低估后续费用。第三轮上下界同时为七元，才得到全局最优证书。若只因两轮选择相同的 $y$ 就停止，会把一个错误费用估计留下。

可行性割与适用条件

本例有无限量外购，所以任何主问题选择都能完成需求。若去掉外购变量，选择 $y = 0$ 后子问题将不可行。此时不能返回一个有限费用割来假装解决；需求与容量直接要求 $5 y \geq 4$ ，这是排除不可补救主决策的可行性割。保留外购时用到的两条则是最优性割，它们只改进后续费用的下界。

一般线性子问题的对偶可行解给出最优性割，适当的不可行性证书给出可行性割；子问题必须被正确求解并区分不可行与无界。若后续变量本身也必须为整数，直接套用其连续松弛对偶通常只给出下界，不能照搬经典线性本德斯的完整性结论。数值实现还须规定割违反容差和上下界停止容差。

本例的有理数实现

以下代码只求解上面的两选择工厂模型，主问题枚举 $y = 0, 1$ ，子问题使用已证明的显式解；它不是通用线性规划求解器。每次新割在当前点都达到真实子问题费用，未获证书时将排除当前的错误低估。本例只有两种主选择，至多加入两条不同割，故循环有限。

Python 3

from fractions import Fraction

def benders_factory(fixed_cost=3):
    fixed_cost = Fraction(fixed_cost)
    if fixed_cost < 0:
        raise ValueError("nonnegative fixed cost required")
    cuts = [(Fraction(0), Fraction(0))]  # eta >= a + b*y
    upper, best_y, trace = None, None, []
    for _ in range(4):
        lower, y, eta = min(
            (fixed_cost*y + max(a+b*y for a,b in cuts),
             y, max(a+b*y for a,b in cuts)) for y in (0,1))
        alpha, beta = (4,3) if 5*y < 4 else (1,0)
        recourse = Fraction(4*alpha-5*y*beta)
        feasible_cost = fixed_cost*y + recourse
        if upper is None or feasible_cost < upper:
            upper, best_y = feasible_cost, y
        trace.append((y, lower, upper))
        if lower == upper:
            return best_y, upper, trace
        cuts.append((Fraction(4*alpha), Fraction(-5*beta)))
    raise AssertionError("two distinct recourse cuts suffice")

y, value, trace = benders_factory()
print(y, value)
print([(y, int(lo), int(up)) for y,lo,up in trace])
# 1 7
# [(0, 0, 16), (1, 4, 7), (1, 7, 7)]

这段特例代码主变量数固定，每轮只比较两个候选；若已有 $k$ 条割，计算量为 $O (k)$ ，保存割与日志也为 $O (k)$ 。一般模型的主问题可能是困难的整数规划，分解并不免除其求解成本。

变式。 开机费改为十三元后，开机总费用十七元，不开机十六元，最优选择转为不开机。运行 benders_factory(13) 得费用十六；两条后续费用割都不变，因为改变的仅是主问题固定费用。这也体现了费用分解与决策比较的区别。

参考文献

↑ Robert M. Freund，MIT，Benders’ Decomposition Methods for Structured Optimization, including Stochastic Optimization (2004)，§2—3.1，第2—10页，补救问题对偶、最优性/可行性割及上下界停止准则。

[1] Robert M. Freund，MIT，Benders’ Decomposition Methods for Structured Optimization, including Stochastic Optimization (2004)，§2—3.1，第2—10页，补救问题对偶、最优性/可行性割及上下界停止准则。

[1]