🧩 Constraint Solving POTD:Problem of the Day: 0/1 Knapsack

[github-actions[bot]]

Problem Statement

You have a knapsack with capacity C and a set of items i, each with a weight w_i and a value v_i. Pick a subset of items that fits within the capacity and maximizes total value. Each item is taken whole or left out (hence "0/1").

Small instance (C = 15):

Item	Weight	Value	Density v/w
A	2	3	1.50
B	3	4	1.33
C	4	5	1.25
D	5	8	1.60
E	9	10	1.11

• Input: capacity C and item pairs (w_i, v_i).
• Output: selection x_i ∈ {0,1} maximizing Σ v_i·x_i subject to Σ w_i·x_i ≤ C.

Optimal answer: take A, B, C, D for weight 14 and value 20. Taking E (weight 9) leaves only 6 units of capacity, which caps the value at 18.

Why It Matters

• Capital budgeting: choose which projects to fund under a fixed budget. This is the textbook application.
• Column generation: the pricing subproblem in cutting-stock and many vehicle-routing solvers is a knapsack-like problem solved thousands of times per run.
• Loading and resource allocation: filling a container, satellite payload, or VM host with the most valuable jobs under a size limit.

Modeling Approaches

1. Integer Linear Programming (MIP)

• Variables: x_i ∈ {0,1} for each item.
• Objective: max Σ_i v_i·x_i
• Constraint: Σ_i w_i·x_i ≤ C

Trade-offs: The LP relaxation (0 ≤ x_i ≤ 1) gives a strong upper bound, and solvers add cover cuts and reduced-cost fixing on top. Side constraints such as cardinality or multiple knapsacks are easy to add. The weakness is instances where values are almost proportional to weights, because the LP gap can stay large.

2. Dynamic Programming (pseudo-polynomial)

• State: dp[c] = best value achievable with capacity at most c.
• Recurrence: for each item, dp[c] = max(dp[c], dp[c - w_i] + v_i), iterating c downward from C to w_i.

Trade-offs: Exact and simple, running in O(nC) time. It is pseudo-polynomial, so it becomes impractical when C is huge (for example 10^9).

3. Constraint Programming (CP-SAT style)

Boolean variables with a linear capacity constraint, plus logical side constraints that are awkward in a pure MIP.

Example Model (Pseudo-code)

# Pseudo-code, OR-Tools CP-SAT style (not executed)
items = {"A": (2, 3), "B": (3, 4), "C": (4, 5), "D": (5, 8), "E": (9, 10)}
C = 15

model = CpModel()
x = {i: model.NewBoolVar(f"x_{i}") for i in items}

# Capacity: total weight of chosen items <= C
model.Add(sum(w * x[i] for i, (w, v) in items.items()) <= C)

# Objective: maximize total value
model.Maximize(sum(v * x[i] for i, (w, v) in items.items()))

# Optional logical side constraint: D and E conflict
model.AddBoolOr([x["D"].Not(), x["E"].Not()])

status = CpSolver().Solve(model)   # expected optimum: 20 (A, B, C, D)

Trade-offs: Logical and conditional constraints (conflicts, "if X then Y") map directly onto clauses, and clause learning handles them well. Pure linear bounds are weaker than the MIP LP bound, so CP-SAT relies more on search and learning.

Key Techniques

1. LP relaxation and greedy bound. Sort items by density v_i / w_i and fill greedily, allowing one fractional item. Here D, A, B, C fit fully (weight 14, value 20). Then 1/9 of E adds 10/9 ≈ 1.11, giving an upper bound of 21.11. Any integer solution is at most 21, and the optimum of 20 is within 1.11 of that bound. Branch-and-bound uses this bound to prune.

2. Dominance. A partial solution (w, v) is dominated if another partial solution has w' ≤ w and v' ≥ v. Discarding dominated states is what makes DP and branch-and-bound fast in practice.

3. Reduction. Remove items with w_i > C before searching. Use reduced costs from the LP to fix variables to 0 when they cannot improve on the incumbent solution.

Challenge Corner

• Recover the solution: the DP table above gives the optimum value 20 at dp[15]. How would you store decisions so you can backtrack and output which items were chosen?
• Large capacity: O(nC) is hopeless for C = 10^9 with 50 items. Which technique would you reach for instead? (Hint: branch-and-bound with the greedy bound, or Horowitz–Sahni meet-in-the-middle at O(2^{n/2}).)
• Uncertainty: suppose each weight lies in [w_i, w_i + δ_i], and at most Γ items can take their worst-case weight. How many extra variables and constraints does a robust version need? (This is the budget-of-uncertainty model of Bertsimas and Sim.)

References

• Kellerer, Pferschy & Pisinger, Knapsack Problems, Springer, 2004. The standard comprehensive reference.
• Martello & Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990.
• Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006.
• Pisinger, "Where are the hard knapsack problems?", Computers & Operations Research, 2005. Explains which instance structures are hardest for exact methods.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~2 AIC · ⌖ ~2 AIC · ⊞ 4.1K · ◷

• expires on Nov 20, 2026, 3:32 AM UTC-08:00