线性规划松弛与舍入

LP 松弛先把难处理的离散可行域扩成可优化的分数多面体，最优值因此成为整数最优的单向界。舍入必须同时完成两件事：把分数点送回组合可行域，并控制目标值相对松弛界的损失；只完成其中一项还不是近似证明。

边界 ​

逐坐标四舍五入可能破坏全局覆盖约束。以四个元素 $\{1,2,3,4\}$ 为例，提供四个成本为 1 的集合 $S_i=\{1,2,3,4\}\setminus \{i\}$。每个元素恰属于三个集合，把每个变量取为 $1/3$，每条覆盖约束的左边都是 1；四个约束相加还给出 $3\sum _i{x}_i\ge 4$，因此这是最优 LP 解。若按 $1/2$ 阈值全舍为零，连一个元素也没有覆盖。顶点覆盖的阈值证明依赖每条约束只有两个端点，不能直接搬到任意集合覆盖。最大化时松弛给上界，近似比的不等式方向相反。若最优 LP 解本身已经是整数点，就无需舍入；但 LP 可在多项式时间内求解，并不保证存在损失很小的舍入规则。

建模质量先于舍入：同一整数问题可有多个 LP。若松弛漏掉关键有效不等式，分数解过于乐观，任何仅按 LP 值证明的比率都受 integrality gap 限制。

证明必须分别建立整数可行性和目标界。只计算舍入后的期望成本，却没有处理违反约束的结果，尚未得到近似算法。

从整数模型到分数解 ​

Vertex Cover 为每点设 $x_v\in \{0,1\}$，每边约束 $x_u+x_v\ge 1$。放宽到 $[0,1]$ 后，三角形可取每点 $1/2$，目标值为 $3/2$。把三条边约束相加得 $2(x_a+x_b+x_c)\ge 3$，所以该值确是 LP 最优值；整数解选一个点会漏掉对面的边，选两个点足够，故整数最优为 2。按阈值 $1/2$ 舍入会选三个点，成本 3，仍不超过 2 倍 LP。

可行性证明逐边看：$x_u+x_v\ge 1$ 意味至少一个端点不小于 $1/2$；成本证明对每个被选点用 $1\le 2x_v$。两条证明缺一不可，且非负加权情形同样逐点乘 $w_v\ge 0$；这个符号条件保证不等号方向保持。

随机舍入与修复 ​

设全集有 $m\ge 1$ 个元素，集合成本 $w_j\ge 0$，并已取得可行集合覆盖 LP 的最优解；空全集直接返回空覆盖。可对每个集合独立以 $p_j=min\{1,c{x}_j\}$ 的概率选择，$c\ge 1$ 是放大因子。由期望的线性性理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。，期望成本 $\sum _j{w}_j{p}_j\le c\sum _j{w}_j{x}_j=cLP$。对一个元素，若某个覆盖它的集合以概率 1 入选，它一定被覆盖；否则未覆盖概率为 $\prod _{j:e\in S_j}(1-c{x}_j)\le e^{-c\sum _{j:e\in S_j}{x}_j}\le e^{-c}$。并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。给出任一元素遗漏的概率至多 $m{e}^{-c}$。这说明对数级放大为何出现，也说明只算期望成本还不够。

随机舍入的集合覆盖证明理路随机舍入randomized rounding从连续松弛解生成随机离散解，以覆盖补选证明每次可行性与期望成本，并区分独立坐标与共享超平面的舍入。固定最便宜补选集，用初选成本与遗漏元素收费共同得到 $(1+\ln m)LP$ 的期望界，并通过八个分支核对去重后的实际费用。若选择重复采样直到可行，也要分析成功概率与运行时间。依赖舍入可以保护特定全局约束，但不是对任意约束的自动修复器。

随机成本的期望界不等于高概率界；需要 Markov/Chernoff、重复取最好可行解或条件期望去随机化，并把求 LP 的多项式成本计入。

松弛选择边界 ​

最小化 LP 值是整数 OPT 下界，最大化则是上界。加强 LP 添加有效不等式可能改善 integrality gap，却增加求解/分离成本。SDP rounding 使用向量几何，不是线性舍入的同义替换。

若目标是精确整数最优，Gomory 分数割理路Gomory 分数割Gomory fractional cut从纯整数单纯形表的一行提取分数部分，用非负性和整数同余推出一条排除当前分数基点的有效割。可从纯整数表行产生一条排除当前分数点的有效不等式；变量含连续分量时需另用适当割式。分支切割理路分支切割法与局部割作用域Branch and cut把有效割嵌入分支定界，在提高松弛上界的同时记录每条局部割的祖先作用域，交出可逐结点核验的最优证书。把有效割与结点分支合并，并为每条局部割记录可复用的子树范围，直到可行解值与全局松弛界相等。