欢迎来到fancyy的博客

先放松整数约束，解对应的线性规划（LP松弛）。

• 如果最优解自动都是整数 → 那就是整数规划的解，结束。

• 如果某个变量 xixi​ 本应是整数，但在 LP 解中是小数（比如 x1=2.3x1​=2.3）→ 就“分支”。

分支：对这个小数变量，分成两个子问题：

• 子问题 A：xi≤2xi​≤2

• 子问题 B：xi≥3xi​≥3
  这样就排除了 2<xi<32<xi​<3 的非整数区域。

定界：每个子问题重新解 LP，得到该分支的目标上界（最大化问题）或下界。

• 如果某子问题的上界 ≤ 当前已知的最优整数解（称为“全局下界”），就剪枝（不再往下分）。

• 如果找到更好的整数解，更新全局下界。

重复，直到所有分支要么被剪枝，要么被完全求解。