全对偶整数性

对偶变量把原不等式加权组合成目标上界。若 $A^{\mathsf{T}}y=c$ 且 $y\ge 0$，对每个可行 $x$ 都有

当 $b$ 和最优 $y$ 都是整数，最紧上界 $b^{\mathsf{T}}y$ 也是整数。TDI 把这件事同时保证给所有整数目标。结合“所有整数目标的有限最优值均为整数”的判据，就得到原可行域的整数性。

在有顶点的情形，也可以直接看反证机制：若某个顶点 $v$ 有分数坐标 $v_i$，选择足够深入其法向锥的整数目标 $c$，让 $c$ 与 $c+e_i$ 都在 $v$ 最优。TDI 与整数右端要求两个目标值都是整数，其差却是 $v_i$，矛盾。证明把对偶证书的整数性传到原始顶点，而不是把一个对偶变量误认为某个原变量。

同一个半直线，两种描述 ​

考虑 $P=\{x:x\le 1\}$。第一种描述就是 $x\le 1$。当整数目标 $c\ge 0$ 时，对偶要求 $y=c$，这显然是整数最优解；当 $c<0$ 时，原问题向负无穷方向使目标无界，不在定义的有限最优范围内。因此第一种描述是 TDI。

把同一条约束乘二，改写为 $2x\le 2$。可行集完全相同，但目标 $maxx$ 的对偶是 $min2y$，满足 $2y=1,y\ge 0$，唯一解 $y=1/2$。于是第二种描述不是 TDI。它仍表示整数多面体，只是这份行列表不允许用整数倍数拼出目标系数 $1$。

若在 $2x\le 2$ 之外再加回冗余行 $x\le 1$，可用第二行承担全部整数目标乘子，得到一份 TDI 描述。冗余行在几何上可能什么都没改变，却能改变整数证书的表达能力。

右端为什么必须另查 ​

系统 $x\le 1/2$ 仍然 TDI：有限的整数目标 $c\ge 0$ 对应 $y=c$。但其端点为 $1/2$，不是整数多面体。对偶目标值为 $c/2$，这一次不是整数的环节正是右端 $b$。

反过来，若一个系统 TDI，不能由此推断矩阵的每个子式都为 $0,\pm 1$。上面加了冗余行的系统含系数 $2$，已经不是TU 矩阵公理库全幺模矩阵与整数顶点Totally unimodular matrix · Total unimodularity · TU用所有方形子式的 0、±1 性质控制逆矩阵分母，证明整数右端的线性约束产生整数顶点。，却可以 TDI。TU 是对矩阵和任意整数右端的强统一条件；TDI 是对当前系统和全部整数目标的条件。

加权匹配的一份整数价格 ​

在二分图 $\{u_0,u_1\}$ 与 $\{v_0,v_1\}$ 的四条边上，权重矩阵为

取交叉匹配 $u_0{v}_1,u_1{v}_0$，总权重 $8$。匹配 LP 的对偶给每个顶点非负价格，要求一条边两端价格之和至少等于边权。价格

满足四条边的覆盖条件，总价也为 $8$。因此原始匹配与整数对偶证书同时最优。这个例子展示 TDI 希望保证的现象；要得到对所有整数边权的结论，仍需二分图关联矩阵的 TU 证明，而不是只核对这一组价格。

TU 矩阵给出 TDI 系统：对整数 $c$，对偶可行域 $\{y\ge 0:A^{\mathsf{T}}y=c\}$ 的等式矩阵与单位界结构仍为 TU，其顶点都是整数；若对偶最优值有限，就可选择一个整数最优顶点。这里并不要求 $b$ 整数，因为 $b$ 只是对偶目标；只有进一步推出原问题整数性时才需要它。

TDI 是组合最小—最大定理的桥梁。一侧是匹配、流等整数对象，另一侧是整数价格、覆盖或割证书；线性强对偶把两侧的数值接起来，TDI 负责确保价格可以选整数。一般匹配的奇集描述公理库一般匹配多胞形的奇集约束Edmonds matching polytope · Odd-set inequalities · Blossom inequalities用全部奇数顶点集的内部边上界补齐一般图匹配凸包，并通过紧奇割的收缩与配对展开解释整数性机制。也具有这种性质，但其证明需要额外的奇集结构，不能沿用二分图行符号变换。

工程上验证一份给定证书很简单：检查 $y\ge 0$、$A^{\mathsf{T}}y=c$、整数性和目标值。但认证整个系统 TDI 是带“所有整数目标”量词的数学任务，不等于调用一次 LP 求解器。改变约束缩放、删除看似冗余的行或把整数变量改为连续变量时，都应重新确认依赖的是哪一层保证。