概念Linear Programming Relaxation / LP Relaxation
线性规划松弛
将整数规划中的整数变量放宽为连续变量，得到多项式时间可解的线性规划，用于估计原问题最优值的界。
时间轴 (近 90 天)
10月17日
标准的0/1背包问题要求决策变量 x_i ∈ {0,1}，直接对离散变量求梯度不可行，常见做法是松弛为连续变量 x_i ∈ [0,1]，此时问题变为线性规划。
待验证50%
10月17日
线性规划松弛是组合优化中一种标准的界估计技术：将整数变量放宽为连续变量后，问题转化为多项式时间可解的线性规划，其最优值给出了原整数问题最优值的上界（最大化问题）。
待验证50%
9月30日
论文方法通过为token出现设定非负价格，用最短路径与词表预算选择得到下界，对价格取最大值恢复线性规划松弛，并用独立整数检查器对数值进行认证
待验证50%