概念

分支定界

通过线性松弛给出界，再对非整数变量分支并剪去不可能更优的子树，系统搜索整数最优解，是商用求解器的核心框架。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

分支定界运筹学

01定义

分支定界是整数规划的精确搜索框架：对子问题求解线性松弛得到下界，界不够好则按非整数变量分支为两个子问题，界劣于已知可行解则剪枝——系统枚举与聪明剪枝的结合，是商用求解器的核心。

分支定界树：剪枝让指数枚举变得可行

松弛越紧、分支树越小：同一个问题，松弛界差 1% 可能意味着节点数差百倍。启发式先找好的初始可行解（上界）同样关键——上下界夹逼终止搜索。

选哪个变量分支：分数性最强的、伪成本估计影响最大的；强分支（strong branching）试算多个候选再选——现代求解器混合多种规则动态选择。

在每个节点先加割平面收紧松弛再分支：分支定界 + 割平面 = 分支切割（Branch & Cut），TSP 百万城市、航班排班等大规模实例的标准武器。

z_{LP}\leq z_{IP},\quad z_{LP}\geq z^{*}\Rightarrow\text{剪枝},\quad x_j\notin\mathbb{Z}\Rightarrow\{x_j\leq\lfloor x_j\rfloor\}\cup\{x_j\geq\lceil x_j\rceil\}

兰德与道伊奇 1960 年提出分支定界框架；巴林斯基与诺曼的隐枚举思想并行发展；1990 年代与割平面结合后成为商用求解器（CPLEX、Gurobi）的标准架构。

车辆路径与航班排班、工厂选址与网络设计、组合拍卖的赢者确定、机器学习中的最优决策树（整数规划形式）。

分支定界：整数规划的搜索树松弛 LP 给出上界；分数解处分支，界差超过当前最优则剪枝

步骤0