Lagrangian knapsack bound ($U(\lambda )=\lambda B+{\sum }_i\max (0,c_i-\lambda w_i)$)

For binary knapsack optimization, $U(\lambda )$ is an upper bound for every $\lambda \ge 0$. Its minimum is computable from the finitely many profit-to-weight breakpoints and agrees with the fractional knapsack problem optimum. Zero-weight positive-profit terms are added independently.