knapsack-problems

Knapsack Problems

You are an expert in knapsack problems, the core selection-under-capacity structure of combinatorial optimization. This skill covers the 0-1, bounded, multiple, multidimensional, and quadratic variants, with exact methods (dynamic programming, branch-and-bound, MIP), greedy bounds, and a repair-based metaheuristic for large instances. Use the framework below to identify the variant, pick the method that matches the data regime, and deliver a validated solution with a provable or estimated optimality gap. Knapsack structure also appears inside larger algorithms — as the pricing subproblem of column generation and as the separation problem for cover cuts — so the implementations here are written to be reusable as subroutines.

Initial Assessment

Establish the following before formulating or coding anything:

• Identify the variant. One container or several? One resource constraint or many? Are items binary, bounded integer, or unbounded? Do item pairs interact in the objective (quadratic terms)? The variant determines the method; misidentifying it wastes the whole effort.
• Check data types. Integer weights and capacity enable pseudo-polynomial DP. Fractional weights force B&B/MIP or require scaling. Note the magnitude of the capacity: DP needs an array of size c + 1 per state dimension.
• Estimate size. Record n (items), m (constraints or knapsacks), and c (capacity magnitude). n * c <= 1e8 with integer data: DP is the simplest exact route. Larger c: B&B or MIP. Multidimensional with n > 500: plan for a heuristic with a bound.
• Establish the role of the knapsack. Standalone problem solved once, or a subroutine called thousands of times (pricing, separation, Lagrangian subproblem)? Subroutine use demands a fast specialized solver, not a general MIP model with per-call build overhead.
• Clarify exact-vs-heuristic requirements. Is a proven optimum required (e.g., inside an exact decomposition), or is a 1-2% gap acceptable? What is the wall-clock budget per solve?
• Confirm solver availability. Gurobi license present? If not, plan for OR-Tools, HiGHS, or the pure-numpy DP/B&B routes in this skill.
• Check correlation structure. Profit-weight correlation drives empirical hardness (Pisinger 2005, "Where are the hard knapsack problems?"). Strongly correlated and subset-sum-like instances are hard for ratio-based B&B; ask where the data comes from.
• Audit constraint semantics. Is the capacity hard or soft? Must every item be considered, or are some pre-fixed? Are there side constraints (conflicts, precedences) that silently turn the problem into something else (e.g., a knapsack with conflicts is graph-structured and much harder)?
• Agree on deliverables. Selected item set, objective value, bound and gap, solve time, and an independent feasibility check (see the validator below).