线性规划松弛是组合优化中一种标准的界估计技术：将整数变量放宽为连续变量后，问题转化为多项式时间可解的线性规划，其最优值给出了原整数问题最优值的上界（最大化问题）。