整数间隙

整数间隙（integrality gap）衡量整数优化模型与其连续松弛之间的最优值差距。连续松弛允许原来必须为整数的变量取分数，通常容易求解，却可能给出无法实际执行的乐观目标值。间隙反映这种松弛有多紧，不等同于某次程序尚未算完留下的误差。

三个互相冲突的候选项目，每个收益一元，任意一对都不能同时选择。令 $x_i\in \{0,1\}$，整数模型为 $$\begin{array}{cc}max& x_1+x_2+x_3,\\ x_1+x_2& \le 1,\\ x_1+x_3& \le 1,\\ x_2+x_3& \le 1.\end{array}$$ 整数方案最多选一个项目，且确实可以选一个，所以 $z_{\mathrm{I}\mathrm{P}}=1$。问题不在于缺少选择方案，而在于连续松弛把互相冲突的三项都“各做一半”视为可行。

精确算出松弛值

把整数约束改为 $0\le x_i\le 1$，取三个二分之一便满足全部约束，收益为 $3/2$。再把三条成对约束相加，得到 $$2(x_1+x_2+x_3)\le 3.$$ 因此任何松弛解都不超过二分之三，这个分数方案又达到该值，故 $z_{\mathrm{L}\mathrm{P}}=3/2$。这里既有达到上界的点，也有证明上界的约束组合，结论不依赖画图猜测。

本实例最大化模型的绝对间隙为 $z_{\mathrm{L}\mathrm{P}}-z_{\mathrm{I}\mathrm{P}}=1/2$；若采用正最优值上的比值定义，则为 $z_{\mathrm{L}\mathrm{P}}/z_{\mathrm{I}\mathrm{P}}=3/2$。说“间隙为二分之一”还是“间隙为一点五”必须附上约定，否则两个正确数字也会造成歧义。

金色虚线距离是该实例的绝对整数间隙。加强松弛后，上界与已知整数方案重合。

定义的方向与前提

对最小化问题，可行域放宽会使目标值下降，故方向相反：$z_{\mathrm{L}\mathrm{P}}\le z_{\mathrm{I}\mathrm{P}}$，绝对间隙通常取 $z_{\mathrm{I}\mathrm{P}}-z_{\mathrm{L}\mathrm{P}}$，正值条件下的比值取 $z_{\mathrm{I}\mathrm{P}}/z_{\mathrm{L}\mathrm{P}}$。若分母为零、最优值为负、不可行或无界，应单独规定，不能机械套用比值。一般还可将LP替换为指定的其他松弛，但必须说明比较对象。

一个实例的间隙是两个最优值的比较；一个问题族或某类建模形式的最坏比值间隙，则是对所有允许实例取上确界。单个三角形例子不能证明其他规模问题的最坏界。

间隙也依赖建模形式。同一批整数可行方案可以对应不同的连续可行域。若增加一个对所有整数方案有效的不等式，连续域缩小，最大化问题的松弛上界不会上升，因而绝对间隙不会变大；最小化时松弛下界不会下降。增加约束是否值得，还须衡量求解成本，不能只数约束条数。

加强模型的具体作用

三项两两冲突已经在整数意义下推出 $x_1+x_2+x_3\le 1$，这是本例的团约束。将其加到连续松弛后，半半半点被排除，松弛最优值变为一，与整数最优相同。它没有删掉任何真正可执行的整数方案；若随意添加不满足这一要求的限制，就不是有效加强。

即使某个目标的整数间隙为零，也不能据此说整个连续多面体的每个顶点都为整数。一个恰好在整数顶点取得最优值的目标，可能掩盖其他方向的分数顶点。全幺模矩阵提供的是更强的、对整数右端所有线性目标都适用的结构结论。

与求解器间隙的区别

整数规划程序在运行中通常维护最佳已知可行值和一个全局界。最大化时可行值是下界，搜索所得上界不必就是根节点连续松弛最优值；它可能已被分支和割进一步改进，甚至根LP都未完整求解。二者距离是当前计算证书的缺口，与这里比较的两个精确最优值不是同一个量。

例如目前已有可行收益一、有效上界一点二，则绝对计算缺口为零点二，而原始LP与IP之间的结构间隙仍为零点五。随着搜索结束，上下界都变成一，计算缺口为零，原始模型的整数间隙并不会因此消失。不同程序对“相对MIP gap”的分母和零值处理也有不同约定，必须查看其定义。

可复算验证与变式

下面枚举八个二进制候选，给出整数最优值；松弛值则由已经证明的二分之三上界及达到该界的点认证。代码没有把有限网格枚举假装成连续最优证明。

Python 3

from fractions import Fraction
from itertools import product

def triangle_gap(profit=1, offset=0):
    profit, offset = Fraction(profit), Fraction(offset)
    if profit <= 0:
        raise ValueError("positive common profit required")
    feasible = [x for x in product((0,1),repeat=3)
                if x[0]+x[1] <= 1 and x[0]+x[2] <= 1
                and x[1]+x[2] <= 1]
    integer = max(offset+profit*sum(x) for x in feasible)
    relaxed = offset+profit*Fraction(3,2)
    ratio = relaxed/integer if integer > 0 and relaxed > 0 else None
    return integer, relaxed, relaxed-integer, ratio

print(triangle_gap())
print(triangle_gap(2))
print(triangle_gap(1,10))
# (Fraction(1, 1), Fraction(3, 2), Fraction(1, 2), Fraction(3, 2))
# (Fraction(2, 1), Fraction(3, 1), Fraction(1, 1), Fraction(3, 2))
# (Fraction(11, 1), Fraction(23, 2), Fraction(1, 2), Fraction(23, 22))

此三变量示范的计算量固定；推广为 $n$ 个二进制变量的全面枚举则有 $2^n$ 个候选，不能当作大规模通法。

变式。 将每项收益同时乘二，IP值二、LP值三，绝对间隙变为一，比值仍为二分之三。若对每种方案统一增加十元常数收益，则IP值十一、LP值十一点五，绝对间隙仍为二分之一，比值却变为 $23/22$。因此绝对间隙随目标单位缩放，比值间隙则对目标平移敏感；二者都应结合原始目标的含义解释。