精确算法
本页是本站「精确算法」类笔记的总览：说明什么叫精确式方法、本库中各篇目的关系与推荐阅读顺序；每篇的推导与步骤仍以各独立页面为准。
什么是「精确式」方法
- 目标：在可终止的前提下，证明所输出解是（混合）整数规划或相应问题的最优解（或证毕问题不可行/无界）。
- 对比：启发式、元启发式、定界不保证的构造式方法通常不给出最优性证明，而追求快速可行解或好近似。
- 代价：许多精确算法的最坏时间随规模指数增长，工程上常配合预处理、割、定界、并行以缩小实际搜索量。
在混合整数规划（MIP）语境下，下面笔记中的分支、割、列生成、分解、拉格朗日等，都可作为精确求解管线中的组成模块。
本库内容结构
0. 线性规划求解内核（与松弛子问题）
- 单纯形法：标准形 LP 上顶点迭代；正文含原始与对偶单纯形骨架；是许多精确管线里反复求解的 LP 松弛子问题的算法基础，也与列生成主问题的求解形式相连。
- 改进单纯形法：不显式存表的紧缩形式（修正单纯形），给出 、、 的计算顺序与基逆更新概要；大规模 LP / MIP 求解的实际内核。
1. 以分支定界（BB）为搜索骨架
- 分支定界：用松弛（如 LP）给上/下界，在变量上分支成子问题，剪枝不能改进全局界的节点。是整数规划最经典搜索范式之一。
- 分支切割：在 BB 节点上加入有效不等式（割），缩小松弛的可行域、收紧界，常显著减少树规模。
- 分支定价：变量极多、难以全部列于模型时，在节点上用列生成按需加列，与 BB 结合。
- 分支定价切割：在分支定价各节点上再叠加割平面，是多种技术的组合形态。
关系速记：都是「树搜索 + 松弛定界」；在 BB 上依次叠加割、列或二者，以应对不同结构难点。
2. 分解与主–子问题结构
- Dantzig–Wolfe 分解：利用块角结构，将大问题写成主问题 + 子问题，常驱动列生成实现。
- Benders 分解：将决策分阶段，用 Benders 割迭代收紧，适合随机规划、多阶段 MIP 等。
- 列生成：大规模线性规划中按约简费用生成列，亦是分支定价的 LP 子问题核心。
关系速记：DW / Benders 是模型层的分解；列生成是算法层在 LP 上的一种求解技术，常与上述分解或分支配套。
3. 对偶与松弛
- 拉格朗日松弛：将难约束乘子化移入目标，得可分解子问题；通过对偶/次梯度等更新乘子。可用于界、分支定界中的界或设计启发，与精确算法常结合使用。
各篇目一览
| 篇目 | 一句话 |
|---|---|
| 单纯形法 | 标准形 LP 顶点迭代；含原始与对偶单纯形骨架 |
| 改进单纯形法 | Revised Simplex：不显式整表， / 定价 / LU 与迭代概要 |
| 分支定界 | 整数规划经典树搜索，松弛定界、分支、剪枝 |
| 分支切割 | BB + 有效不等式（割） |
| 列生成 | 大规模 LP，按需加列 |
| 分支定价 | BB + 列生成 |
| 分支定价切割 | 分支定价 + 割 |
| Dantzig–Wolfe 分解 | 块角结构，主问题–子问题、常见列生成就位 |
| Benders 分解 | Benders 割迭代，多阶段/分解结构 |
| 拉格朗日松弛 | 难约束乘子化，可分解、给界、调乘子 |
建议阅读顺序（可选）
- 若关心理论主线：若 LP 松弛与检验数、基变换尚不熟，可先浏览单纯形法（含对偶骨架）→ 改进单纯形法 → 分支定界 → 分支切割 → 需要大规模变量时看列生成 / 分支定价 → 再视需要看 BPC、DW、Benders。
- 若更关心界与可分解子问题：拉格朗日可较早阅读，并回到分支定界/定价语境下理解其用法。
- 各篇中的算法框、数学形式与实现细节，均以对应独立页面为准。
图论上的最短路（Dijkstra、Bellman-Ford 等）属于另一导航分组「图算法」，其多数情形同样是在声明的模型上精确求解到最优；与 MIP 精确算法在应用上可并列参考。