整数优化与离散决策

配送中心可以把货物拆成连续的小数，但车辆、班次和项目通常不能。把一个连续模型的答案四舍五入，看起来省事，却可能违反容量、覆盖或逻辑条件。整数优化要回答的是：在离散可行集合中，怎样找到一个可证明的好方案。

整数约束改变了可行集合

最大化问题的线性松弛允许变量取实数。整数模型则要求某些变量 $x_j\in\mathbb Z$，二元变量还要求 $x_j\in\{0,1\}$。松弛模型的可行域更大，因此其最优值是整数最大化问题的上界；对最小化问题则是下界。

若松弛解恰好整数，它立刻也是整数最优解。若不整数，四舍五入没有一般正确性：可能让某条“最多”约束超标，也可能得到一个可行但很差的整数点。

分支定界的两个数字

设一个整数最大化模型的松弛最优值为 18.7，当前已经找到一个可行整数解，收益为 16。18.7 是该节点的上界，16 是 incumbent（当前最好整数解）。如果另一个节点的松弛上界只有 15.4，它不可能产生比 16 更好的整数解，可以剪枝。

分支发生在一个分数变量上，例如 $x_1=2.4$，拆成 $x_1\le2$ 和 $x_1\ge3$ 两个子问题。两个子问题覆盖所有整数可能性，却互不重叠。每个节点都要记录：是否不可行、松弛解是否已整数、上界是否不超过 incumbent。

一个小型背包例子

有容量 9 的背包，物品 A、B、C 的重量和价值分别为 $(4,8),(5,9),(6,12)$，每件最多选一次。模型为

整数可行方案中，A+B 的价值 17，A+C 超容量，B+C 超容量，单个 C 价值 12。若松弛允许部分物品，可能在 C 上取 $1/2$ 并产生一个大于 17 的上界；这个上界可以指导搜索，却不能直接装入背包。

切平面提供另一种思路：找到一个所有整数解都满足、但当前分数松弛解违反的线性不等式，把它加入模型切掉这块分数区域。切平面和分支定界可以结合；本课只要求理解它为什么有效，不把算法实现细节当作黑箱。

练习

1. 某整数最大化问题的当前 incumbent 为 42。一个未展开节点的 LP 松弛上界为 41.5。该节点为什么可以剪枝？

2. 一个松弛解给出 $x_1=3.6$。写出标准分支，并说明为什么没有漏掉整数解。

3. 为什么 integrality gap 大并不表示整数模型写错？