Linear Programming Relaxation
The relaxation of integer variables in an integer program into continuous variables, yielding a linear program solvable in polynomial time, used to estimate bounds on the optimal value of the original problem.
Timeline (last 90 days)
The standard 0/1 knapsack problem requires decision variables x_i ∈ {0,1}; directly computing gradients over discrete variables is infeasible, and a common approach is to relax to continuous variables x_i ∈ [0,1], at which point the problem becomes a linear program.
Linear programming relaxation is a standard bound-estimation technique in combinatorial optimization: after relaxing integer variables to continuous variables, the problem becomes a linear program solvable in polynomial time, and its optimal value gives an upper bound on the optimal value of the original integer problem (for maximization problems).
The paper's method assigns non-negative prices to token occurrences, obtains a lower bound via shortest-path and vocabulary budget selection, recovers the LP relaxation by taking the maximum over prices, and certifies the values with an independent integer checker.
All Facts (3)
The standard 0/1 knapsack problem requires decision variables x_i ∈ {0,1}; directly computing gradients over discrete variables is infeasible, and a common approach is to relax to continuous variables x_i ∈ [0,1], at which point the problem becomes a linear program.
50%UnverifiedLinear programming relaxation is a standard bound-estimation technique in combinatorial optimization: after relaxing integer variables to continuous variables, the problem becomes a linear program solvable in polynomial time, and its optimal value gives an upper bound on the optimal value of the original integer problem (for maximization problems).
50%UnverifiedThe paper's method assigns non-negative prices to token occurrences, obtains a lower bound via shortest-path and vocabulary budget selection, recovers the LP relaxation by taking the maximum over prices, and certifies the values with an independent integer checker.
50%