整数多面体与整数包

整数包把可行整数方案保留下来，再填入它们之间的凸组合。线性目标在一个凸组合上的值，是各整数方案目标值的加权平均，不会超过其中最好的方案。因此在线性优化看来，整数点集合与其凸包有相同的最优值。

原松弛 $P$ 若比整数包更大，就可能有某个目标方向把那一块多出来的分数区域暴露出来。整数性要求对所有目标方向都没有这样的漏洞，比“这次恰好求到整数解”强得多。

在有界情形，顶点判据十分直接。多胞形是其顶点的凸包；若顶点全是整数点，整个多胞形就在整数包内。反过来，一个分数顶点不可能是可行整数点的非平凡凸组合，否则就不是极点。无界但 pointed 的有理多面体还含衰退射线；这些射线可选整数方向，沿整数步长之间插值，仍能用整数点的凸组合填满。几何中的“无界”本身不是障碍，遗漏直线部分才是顶点判据失效的原因。

同一个可行域，不同目标揭示不同问题 ​

令

它的顶点为 $(0,0),(3/2,0),(1,1),(0,3/2)$。非负整数点必须满足 $x,y\le 1$，故恰有

它们的凸包为单位正方形 $[0,1{]}^2$，严格小于 $P$。最大化 $x$ 时，LP 给 $3/2$，整数最优为 $1$，直接看出损失。但最大化 $x+y$ 时，两者都在 $(1,1)$ 达到 $2$。后一目标没有间隙，并不能证明整个松弛整数。

再看已经整数的单位正方形，最大化 $x$ 的最优面是右边整条线段。$(1,1/2)$ 也是 LP 最优解，只是存在同优的整数端点 $(1,0),(1,1)$。所以“整数多面体”不意味着其中没有分数点，也不意味着任意求解器返回的最优点都自动整数；通常需要取得最优顶点，或在最优面内继续寻找整数解。

没有顶点时，空泛判断会出错 ​

集合

是一条有理仿射直线，没有顶点，也没有整数点。于是 $L_I=\varnothing \ne L$。若只检查“所有顶点整数”，得到的真命题只是空集上的全称命题，对实际整数可行性毫无保证。

相对地，直线 $x=0$ 是整数多面体：任意 $(0,y)$ 都位于相邻两个整点 $(0,\lfloor y\rfloor )$、$(0,\lceil y\rceil )$ 的线段上。两条直线都没有顶点，但其极小非空面就是整条直线；“极小面包含整数点”的判据能区分它们。

整数目标值也能检测整数性 ​

对有理多面体，还有一个常用等价判据：每个整数系数目标 $c$，只要最大值有限，该最大值就是整数。整数多面体显然具有这个性质，因为可以用整数最优点计算目标。

为什么反向有力量？在 pointed 情形，若顶点 $v$ 的第 $i$ 个坐标不是整数，选一个整数目标 $c$，使 $v$ 是唯一最优顶点。把 $c$ 放大足够多后，$Mc$ 与 $Mc+e_i$ 仍在同一个顶点的法向锥内部，仍由 $v$ 最优。两最优值之差恰为 $v_i$，不可能两者都是整数。这说明分数顶点总能被适当的整数目标检出，而不一定被手边第一个目标检出。一般含直线情形可用极小面及其有理仿射空间作对应论证。

线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。因此能直接处理某些看似离散的问题，前提是已有整数性定理。全幺模性公理库全幺模矩阵与整数顶点Totally unimodular matrix · Total unimodularity · TU用所有方形子式的 0、±1 性质控制逆矩阵分母，证明整数右端的线性约束产生整数顶点。从约束矩阵出发，对所有整数右端给出保证；全对偶整数性公理库全对偶整数性Total dual integrality · TDI要求每个整数目标都有整数的最优对偶证书，说明这一性质为何依赖不等式表示，以及整数右端如何传递原问题整数性。则从整数对偶证书出发，对特定不等式系统给出保证。

整数性间隙公理库整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。衡量某个目标或某个实例族的松弛损失；整数多面体描述的是整个集合与全部线性目标的精确关系。向 $P$ 加有效不等式时，理想目标是逐步接近 $P_I$，但整数包可能需要很多面来描述，不能把它的存在当作一份已经高效可得的表示。