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

[github-actions[bot]]

Problem Statement

The 0/1 Knapsack Problem is one of the most iconic optimization problems in computer science and operations research. It asks: given a set of items, each with a weight and a value, select a subset of items that maximizes total value without exceeding a weight capacity.

Concrete Instance:

Imagine you're a thief with a knapsack of capacity 15 kg. You have access to these items:

Item	Weight (kg)	Value ($)
Gold Bar	5	50
Laptop	4	40
Jewelry Box	3	30
Camera	2	15
Watch	2	20

Question: Which items should you take to maximize value while staying within 15 kg?

Input/Output:

• Input: n items with weights w_i and values v_i, and capacity C
• Output: A selection (subset) of items maximizing Σv_i such that Σw_i ≤ C

---

Why It Matters

Financial Portfolio Optimization: Investors select assets (stocks, bonds, projects) to maximize expected return within a budget or risk constraint. Each asset has an expected value and a capital requirement.

Manufacturing & Cutting: Factories must select production orders or material cutting patterns that maximize profit while respecting machine capacity or raw material limits.

Cloud Resource Provisioning: Allocating VMs or containers to meet service demand while minimizing cost—each service has value (revenue) and cost (compute/memory footprint).

Inventory Management: Retailers select which products to stock given shelf space constraints and varying profit margins.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Paradigm: Mathematical Programming

Decision variables: x_i ∈ {0, 1} for each item i (1 = take, 0 = leave)

Model:

maximize:  Σ v_i · x_i
subject to: Σ w_i · x_i ≤ C
            x_i ∈ {0, 1}

Trade-offs:

• ✓ Highly optimized solvers (CPLEX, Gurobi, HiGHS) with strong bounds and cuts
• ✓ Directly expresses the problem structure
• ✗ General-purpose ILP solvers may scale poorly for very large instances
• ✗ Limited ability to exploit problem-specific structure (e.g., item groupings)

Approach 2: Constraint Programming (CP)

Paradigm: Declarative Logic with Propagation

Decision variables: x_i ∈ {0, 1} for each item

Constraints:

sum(w_i · x_i for i in 1..n) <= C
maximize: sum(v_i · x_i for i in 1..n)

Trade-offs:

• ✓ Efficient propagation via global constraints (knapsack constraint)
• ✓ Easy to add auxiliary constraints (e.g., "items must be selected in groups")
• ✓ Fast for medium-sized instances with tight capacity
• ✗ Weaker continuous relaxation bounds than ILP
• ✗ Not the best choice for very large instances without hybrid techniques

Approach 3: Dynamic Programming

Paradigm: Tabulation / Memoization

Recurrence:

DP[i][w] = max value using items 1..i with capacity w
DP[i][w] = max(
  DP[i-1][w],                    // don't take item i
  DP[i-1][w - w_i] + v_i         // take item i (if w_i ≤ w)
)

Trade-offs:

• ✓ Polynomial time: O(n·C) — guaranteed, no randomness
• ✓ Simple, implementable in any language
• ✗ Space complexity O(n·C) can be prohibitive for large capacity C
• ✗ Doesn't scale to large weights (e.g., C = 10^9)
• ✗ No flexibility for variants (multiple constraints, non-linear objectives)

Example: MiniZinc Model

% 0/1 Knapsack in MiniZinc
int: n = 5;
array[1..n] of int: weight = [5, 4, 3, 2, 2];
array[1..n] of int: value = [50, 40, 30, 15, 20];
int: capacity = 15;

var 0..1: x[1..n];

constraint sum(i in 1..n) (weight[i] * x[i]) <= capacity;

solve maximize sum(i in 1..n) (value[i] * x[i]);

output [show(x)];

Run with: minizinc knapsack.mzn

---

Key Techniques

1. Dynamic Programming with Space Optimization

For instances where capacity is moderate (≤ 10^6), DP is the go-to approach. The 1D recurrence can be optimized to O(C) space by processing items in reverse order, avoiding a 2D table.

2. Branch & Bound with LP Relaxation

Relax 0/1 variables to continuous [0, 1]. The resulting linear program is solved in O(n log n) via a greedy algorithm: sort by value-to-weight ratio, fill greedily. This LP bound prunes many branches during search.

3. Symmetry Breaking & Preprocessing

• Item dominance: If item A has weight ≤ B's weight AND value ≥ B's value, exclude B
• Capacity bound tightening: Remove items whose weight exceeds remaining capacity
• Core algorithm: Partition items into "core" (might be selected) vs. "must exclude" based on ratio heuristics

---

Challenge Corner

Question 1: The standard 0/1 knapsack has one constraint. How would you model multi-dimensional knapsack (e.g., weight AND volume limits)? Would DP still be efficient?

Question 2: Real thieves care about uncertainty—item weights and values aren't exactly known. How would you reformulate this as a robust optimization problem? What constraints would encode "worst-case" scenarios?

Question 3: In a CP solver, global constraints like knapsack() sometimes achieve better propagation than decomposing into arithmetic constraints. Can you think of a domain reduction that the knapsack() constraint can perform that a simple sum() constraint cannot?

---

References

1. Martello, S., & Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. — The definitive reference; covers DP, branch & bound, and approximation.

2. Pisinger, D. (2005). "Where are the hard knapsack problems?" Computers & Operations Research, 32(9), 2271–2284. — Explores phase transitions and problem difficulty.

3. SICStus Prolog Knapsack Constraint. (sicstus.sics.se/redacted) — Example of a native global constraint in a CP system.

4. Hooker, J. N. (2012). Integrated Methods for Optimization. Springer. — Chapter on hybrid CP/integer programming approaches to knapsack variants.

---

Did this problem intrigue you? Next time, we'll explore a problem that combines scheduling and routing—the Pickup & Delivery Problem. See you then! 🎯

Generated by 🧩 Constraint Solving — Problem of the Day · 32.8 AIC · ⌖ 4.42 AIC · ⊞ 25.4K · ◷

• expires on Jun 17, 2026, 4:37 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #38606.