整数规划
把"变量必须是整数"这一条加进去，问题的性质就彻底变了。线性规划有多项式算法，整数规划是 NP 困难的；可行域从一块连续的多面体，变成一堆孤立的格点。这一页想说明的是：为什么不能"先解松弛再四舍五入"，以及分支定界和割平面究竟在做什么。
LAB 01
松弛与取整的陷阱
线性松弛的解四舍五入，为什么常常既不可行也不最优
问题
买 2.7 台机器是没有意义的。那把线性规划的解四舍五入不就行了？这一台展示为什么不行：取整之后的点可能不可行，即使可行也可能离最优很远，而且维数越高偏得越离谱。
模型
整数规划与它的线性松弛。
IP: max cTx, Ax ≤ b, x ∈ ℤn≥0 ⊂ LP 松弛: x ∈ ℝn≥0
整数间隙 gap = zLP − zIP ≥ 0
LP 松弛的最优值永远是 IP 的一个上界（最大化时），这是分支定界能剪枝的全部依据。而当约束矩阵是全幺模的（如指派、网络流），松弛解自动是整数——那时候松弛就是精确解。整数间隙 gap = zLP − zIP ≥ 0
LP 松弛最优—
四舍五入之后—
真正的整数最优—
松弛上界与整数最优的差—
默认参数下，松弛解是 (3, 1.5)，四舍五入成 (3, 2)——不可行。退一步取 (3, 1)，可行，目标值 19。但真正的整数最优是 (4, 0)，目标值 20，它离松弛解足足有一个格子远，靠"就近取整"永远也找不到。这就是整数规划最容易被低估的地方：松弛解只是一个上界，它的位置并不指示整数最优在哪里。把 b₂ 拖到 8，四舍五入恰好就是最优；拖到 11，取整只能退到 (0, 5) 得 20，而真正的最优是 (2, 3) 得 22，差了 10%。两种情况看起来没有任何区别，而你事先无法知道自己在哪一种里。顺带一提，如果约束矩阵是全幺模的（比如网络流、指派问题），松弛解本身就一定是整数，那时候才真的可以"解完就用"。
LAB 02
分支定界树
看搜索树怎么长、界怎么剪枝，剪掉了多少节点
问题
整数规划是 NP-难的，可求解器却能在几秒内解掉上万个变量的问题。它靠的不是穷举，而是"证明大部分分支不用看"。这一台把那棵搜索树画出来，看界是怎么剪掉它的。
模型
分支定界：分支制造子问题，定界证明子问题不用看。
分支：xj ≤ ⌊x̄j⌋ 与 xj ≥ ⌈x̄j⌉； 剪枝：zLP(节点) ≤ 当前最好整数解 ⟹ 整枝丢弃
剪枝的效率取决于界有多紧——所以现代求解器把大量力气花在"让松弛更紧"上（割平面、预处理）。这一台的"按什么顺序搜"滑杆能直接看到搜索策略对树大小的影响。已展开 / 总共展开的节点数—
被剪掉的节点数—
当前最好整数解—
当前全局上界—
把"用界剪枝"关掉，看节点数怎么变。默认这组数据（10 件物品）：最佳优先 + 剪枝，一共只展开 33 个节点就拿到最优值 94；关掉剪枝，同样的搜索要展开 1050 个——差 32 倍。把物品数拉到 14 或 16，不剪枝那一栏会直接撞上 4000 个节点的上限（读数后面出现 ⚑），而剪枝那一栏仍然只要三四十个。剪枝的逻辑只有一句话：如果这个子问题的上界还不如手上已有的整数解好，它下面所有分支都不用看了。这一句话就是分支定界能在实际问题上跑得动的全部原因——它并没有改变最坏情况的复杂度，只是让绝大多数分支根本没机会展开。也正因为这样，先找到一个好的可行解非常重要：手上的整数解越好，剪掉的分支就越多。工程上常见的做法是先用启发式跑出一个不错的解喂给求解器，这往往比调求解器参数管用得多。最后对比两种搜索顺序：同样开着剪枝，最佳优先 33 个节点，深度优先要 358 个；但深度优先内存占用小、能更快拿到第一个可行解。真实求解器两者混用。
LAB 03
割平面
一刀一刀削掉非整数顶点，可行域慢慢逼近整数壳
问题
与其在搜索树上硬拼，不如把可行域本身削得更接近整数点——削掉那些只含分数解的角。这就是割平面，戈莫里 1958 年的想法，也是今天求解器速度的一半来源。
模型
割平面：加入对所有整数可行解成立、但割掉当前分数最优解的不等式。
对任意整数解满足 aTx ≤ β，而当前 LP 最优 x̄ 满足 aTx̄ > β； 目标是逼近整数壳 conv(XIP)
整数壳（所有整数可行解的凸包）上做 LP 就直接得到 IP 的解，但整数壳的不等式数量一般是指数的。实践中只加"有用的"几刀，和分支定界配合成分支切割法。当前松弛最优值—
当前松弛最优解—
是不是整数解了—
离整数最优还差多少—
每加一刀，可行域就削掉一块，但一个整数点都不会被削掉。这是割平面法的核心要求：割掉的必须只有分数顶点。Gomory 割是从单纯形表里直接读出来的——取一行基变量取值为分数的方程，把所有系数取小数部分，利用"整数的非负组合还是整数"就能推出一条有效不等式。勾上"画出整数壳"：那个由所有可行整数点围成的最小凸多边形，就是理论上的终点。如果一开始就知道整数壳，整数规划就退化成线性规划了——可惜它的面数一般是指数级的，所以只能一刀一刀地逼近。实践中割平面很少单独用，而是和分支定界合成"分支切割"，这是今天所有商用求解器的主力算法。
LAB 04
0-1 背包与指派
两个最常考的模型，动态规划与匈牙利算法的解法对照
问题
背包和指派是建模里出现频率最高的两个模板。有意思的是：一个只能靠动态规划（而且是伪多项式的），另一个却有多项式的精确算法。差别在哪儿？在约束矩阵的结构。
模型
两个模型的标准写法。
背包：max Σ vixi, Σ wixi ≤ W, x ∈ {0,1}n → DP O(nW)
指派：min Σ cijxij, 行列和为 1 → 匈牙利算法 O(n³)
指派问题的约束矩阵是全幺模的，所以 LP 松弛自动整数；背包不是，它的 DP 复杂度含 W，是伪多项式——W 用二进制编码时长度是 log W，所以这仍然是指数的。指派：min Σ cijxij, 行列和为 1 → 匈牙利算法 O(n³)
精确解的目标值—
贪心解的目标值—
贪心差了多少—
与暴力枚举的对照—
这两个模型都是整数规划，但都不用分支定界。0-1 背包有伪多项式的动态规划（O(nW)），指派问题有匈牙利算法（O(n³)）；指派问题之所以这么好解，是因为它的约束矩阵全幺模，线性松弛的最优解天然就是 0-1 的。再看贪心：背包按"性价比"排序装，通常很接近但不保证最优；指派按"每人挑当前最便宜的任务"更容易吃亏。换几组数据，看贪心什么时候失手。最后那个读数是自检——两种算法的结果都拿去和暴力枚举对过，这是写优化代码时最值得养成的习惯：小规模上一定要有一个"笨但一定对"的参照。
这一页想说的
整数规划的难，不在于"多了一个整数条件"，而在于这个条件把凸性毁掉了。所有的技术——分支、定界、割平面、启发式初始解——都是在想办法把非凸问题重新装回一串凸问题里去解。建模时最实际的两条建议是：一、能用连续变量就别用整数变量，能用 0-1 就别用一般整数；二、花时间把模型写紧（更强的不等式、更少的对称性），往往比换一个更贵的求解器有用得多。