线性规划松弛

线性规划松弛（linear programming relaxation）从整数线性规划中删除整数取值要求，保留线性目标、约束及变量界，得到一个连续线性规划。原先的整数可行方案仍然可行，新增的分数点则可能把最优值推到更有利的位置；这种变化使松弛可以给原问题提供可靠界限。

考虑以下二维整数问题： $$\begin{array}{cc}max& 3x+2y,\\ 2x+y& \le 4,\\ x+2y& \le 4,\\ x,y& \ge 0,x,y\in \mathbb{Z}.\end{array}$$ 只删掉最后的整数条件，得到的多边形中便允许 $x=y=4/3$。这是两条资源边界的交点，目标值为 $20/3$。

用约束组合证明松弛最优

仅计算一个交点还不足以证明最优。把第一条资源约束乘 $4/3$，第二条乘 $1/3$ 后相加，得到 $$\begin{array}{cc}3x+2y& =\frac{4}{3}(2x+y)+\frac{1}{3}(x+2y)\\ & \le \frac{4}{3}\cdot 4+\frac{1}{3}\cdot 4=20/3.\end{array}$$ 所有松弛可行点都受这个界约束，交点又恰好达到它，所以松弛最优值确为 $20/3$。这也是一个线性规划对偶证书的具体样子：非负乘子把资源限制变成目标的上界。

着色区域允许连续坐标；原问题只保留其中的格点。分数交点给出上界，不是原问题可实行的选择。

原整数问题的完整比较

由 $2x+y\le 4$ 和非负性，整数 $x$ 只能为零、一、二。固定它后，因目标中 $y$ 系数为正，应取允许的最大整数： $$y=\lfloor min\{4-2x,(4-x)/2\}\rfloor .$$ 三种切片给出 $(0,2),(1,1),(2,0)$，目标依次为四、五、六，故原问题最优为 $(2,0)$、最优值六。

还可以用整数目标加强证书：由于 $3x+2y$ 本身必为整数，且不超过 $20/3$，必然不超过六。再结合已经达到六的可行点，无须继续分支就能确认最优。若目标系数任意为实数，则不能直接沿用这种向下取整的目标界。

上下界与集合包含

一般地，记整数可行集为 $F\subseteq P$，其中 $P$ 为松弛域。最大化且最优值有限时， $$\begin{array}{cc}{c}^{𝖳}\hat{x}& \le z_{\mathrm{I}\mathrm{P}}\le z_{\mathrm{L}\mathrm{P}}\\ & (\hat{x}\in F).\end{array}$$ 左边因为最优值至少和任意可行值一样好，右边因为在更大的集合上寻找最大值不会更差。最小化时方向相反，松弛给下界。松弛最优解如果已经满足整数限制，便同时解决了原问题。

主例把 $(4/3,4/3)$ 四舍五入成 $(1,1)$，虽然可行，却只得到五；向上取成 $(2,2)$ 更会违反两条资源约束。舍入并不保留最优性，甚至未必保留可行性。

变式。 把两条资源上限都从四改成三。相同乘子给目标上界五，而整数点 $(1,1)$ 达到五，故这次松弛与整数最优值相等。松弛是否精确既取决于约束结构，也取决于具体数据；不能从某一次出现整数解，就断言所有右端数据都如此。

对于混合整数线性规划，仅指定的整数坐标被放宽，原本连续的变量继续连续。对非线性整数模型，删掉整数要求通常得到非线性松弛，不能仍把它称为线性规划。把松弛当作求界与诊断工具，比把分数解直接当成最终方案更有数学依据。