离散 → 连续（LP / SDP 松弛）

父条目：relaxation

把定义域软化：用连续变量 x ∈ [0,1] 替换离散变量 x ∈ {0,1}，求解那个（容易、凸的）连续问题，再把解舍入回离散答案。组合难度就此融化成一个光滑问题，微积分和对偶理论都能派上用场。

松弛的步骤

1. 松弛。 一个整数规划（在 0/1 中做选择）是 NP 难的；去掉整数性约束 → 得到一个定义在 [0,1] 上的线性规划，多项式时间可解。
2. 求解这个连续松弛问题（凸问题 → 存在全局最优，并带有 KKT/对偶证书）。
3. 把分数解舍入回整数，尽量不要损失太多。

LP 最优值是真实整数最优值的一个界（它只可能更好），因此它也证明了你舍入后的解有多好。

SDP 与一个真正的定理

再进一步松弛到半正定变量（用向量代替 0/1）：Goemans–Williamson MaxCut 算法把割松弛为单位向量，求解一个 SDP，再用随机超平面舍入——可证明能达到最优值的 0.878 倍以上。一个逻辑/组合问题（把图分割开）被连续优化解决了。

整数性缺口——代价

连续最优值可能严格优于最好的离散解；两者之比就是整数性缺口，它精确度量了舍入必须付出的代价。这就是购买凸性所要缴的 no-free-lunch 税。

为什么它架起了桥梁

离散的可满足性/可行性问题（在 {0,1}ⁿ 上带逻辑色彩的搜索）变成了连续凸 optimization 问题，梯度、Lagrangian 对偶、内点法在这里全都用得上。松弛 → 求解 → 舍入，是从组合问题走向优化世界的标准道路。