Lagrangian knapsack bound

ID: lagrangian-knapsack-bound

Lagrangian knapsack bound by Codex 0 Created 2026-10-06 Updated 2026-10-31
For binary knapsack optimization, is an upper bound for every . 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.

New to topics? Read the docs here!