整数性间隙 | Codeboy's Blog

形式陈述

定义方向

固定一族非负目标的整数优化实例，以及保持目标不变、扩大可行域的线性规划松弛。以下只比较两侧最优值有限、且比值分母严格为正的实例。最小化问题的 gap 为

\sup_I\frac{\operatorname{OPT}_{int}(I)} {\operatorname{OPT}_{relax}(I)},

最大化取相反方向 $\operatorname{OPT}_{relax}/\operatorname{OPT}_{int}$ ，使比值至少 1。Instance gap 是单个实例的比值，integrality gap 通常指指定实例族上的最坏上确界。

分母为 $0$ 的实例需要另立约定：两侧都为 $0$ 时常约定比值为 $1$ ，分子正而分母为 $0$ 时常记为 $+\infty$ ；也可以排除这些实例，转而报告加性差值。这里的“relax”是松弛问题的最优值，不能用求解器尚未收敛时的某个可行分数值代替。

上下界是两种证明任务

最小化时，证明 gap 至多 $\alpha$ ，须对每个实例证明存在成本至多 $\alpha\operatorname{OPT}_{relax}$ 的整数解；舍入定理给出一种构造性证明，但存在性论证也足够。最大化时则要证明存在价值至少 $\operatorname{OPT}_{relax}/\alpha$ 的整数解。证明 gap 至少 $\alpha$ ，只需构造实例族 $I_n$ ，使相应比值趋近 $\alpha$ 。

三角形 vertex cover 的整数最优值为 2，标准 LP 可令每个顶点取 $1/2$ ，值为 $3/2$ ，所以该实例 gap 是 $4/3$ 。它只是一个下界实例，并没有证明最坏 gap 为 2。

对 $n\ge2$ ，完整图 $K_n$ 的最小 vertex cover 有 $n-1$ 个顶点。把全部边约束相加，得 $(n-1)\sum_vx_v\ge n(n-1)/2$ ，因此 LP 值至少为 $n/2$ ；每点取 $1/2$ 达到该界，确为最优。比值

\frac{n-1}{n/2}=2-\frac2n

趋近 2，给出标准 LP gap 至少为 2；经典阈值舍入又给出至多 2，于是上下界吻合。

直觉

Gap 属于松弛而非问题名称

Gap 是“实例族加松弛族”的性质，不是 LP 求解器的数值误差，也不是优化问题脱离公式后的固定常数。加入奇环约束、有效不等式或更高层层级会改变可行分数域，得到的是一个新松弛与新的 gap。

使用 SDP、局部搜索或输入的额外结构也可能突破旧 LP gap。这不表示算法“战胜了”针对该松弛的下界，而是它的证明信息已经不只来自旧分数最优值。

三角形顶点覆盖的分数最优值与整数最优值形成三分之四间隙 — 整数最优与松弛最优的间隙

例子与边界

Gap 对舍入算法的限制

对最小化问题，若算法的全部保证是

\operatorname{cost}(A(I)) \le\alpha\operatorname{OPT}_{relax}(I),

那么 gap 实例迫使 $\alpha$ 至少达到该 gap，否则会声称一个比整数最优值更小的整数解。这个限制针对“只以该松弛值为下界”的分析路线，不是所有可能算法。

Additive gap 衡量两最优值之差，适合某些分母很小的情形，但不能与乘法近似比互换。报告 gap 时应明确最小化/最大化方向、实例族、具体松弛以及零最优值约定。

推论与应用

整数性间隙同时给出舍入分析的目标与障碍：上界通常来自把任意分数最优解舍入，并把所得近似比与 gap 对齐；匹配下界则由坏实例族证明该松弛无法支撑更强比率。加入有效不等式、提升到更强层级或改用半定松弛后，应把它视为新松弛并重新测量 gap。

若要说明一个有理松弛对所有有限线性目标都没有整数损失，应研究整数多面体，而不只展示某个目标恰好没有 gap。若需要逐轮加强松弛，Chvátal–Gomory 闭包把一轮所有整数法向取整纳入同一几何对象；闭包轮数与某个固定目标的 gap 是不同的度量。

参考资料

Vijay Vazirani, Approximation Algorithms, 2001.
Williamson, Shmoys, 2011.
Alexander Schrijver, Combinatorial Optimization, 2003.

形式陈述 ​

定义方向 ​

上下界是两种证明任务 ​

Gap 属于松弛而非问题名称 ​

Gap 对舍入算法的限制 ​

反向链接

形式陈述

定义方向

上下界是两种证明任务

Gap 属于松弛而非问题名称

Gap 对舍入算法的限制