Problem Statement

You have a knapsack with a weight capacity W and a set of n items. Each item i has a weight w_i and a profit p_i. The goal is to select a subset of items to maximise total profit without exceeding the capacity.

Small concrete instance (n = 6, W = 15):

Optimal selection: items {1, 3, 4, 5} → total weight 14 ≤ 15, total profit 25.

Input: n items with weights w[] and profits p[], capacity W.
Output: a 0/1 selection vector x[] maximising ∑ p_i · x_i subject to ∑ w_i · x_i ≤ W.

Why It Matters

• Supply chain & logistics — selecting which orders or shipments to fulfil given a vehicle's weight/volume limit is a daily operational decision.
• Portfolio optimisation — choosing which projects to fund under a fixed budget mirrors the 0-1 knapsack exactly; multi-dimensional variants capture multiple resource constraints (budget, headcount, time).
• Compiler register allocation — deciding which values to keep in fast registers versus spilling to memory is structurally a knapsack problem.

Modeling Approaches

Approach 1 — Constraint Programming (CP)

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

Model:

maximise  ∑ p_i · x_i
subject to
  ∑ w_i · x_i ≤ W          // capacity constraint
  x_i ∈ {0, 1}  ∀ i
```

CP solvers handle this directly, but the key power comes from the **`knapsack` global constraint** (available in MiniZinc, OR-Tools CP-SAT, Choco). This single constraint encapsulates the capacity bound *and* propagates lower/upper bounds on profit simultaneously, enabling much stronger pruning than a naive sum constraint.

**Trade-offs:** Very expressive; global constraint gives strong propagation; less competitive than DP or LP-relaxation on pure instances, but shines when combined with other constraints.

#### Approach 2 — Mixed Integer Programming (MIP)

The same model translates directly to a 0-1 MIP. The LP relaxation (dropping integrality) yields:

```
LP bound:  ∑ p_i/w_i · x_i  (sorted by density, fractional last item)
```

This is solved in O(n log n) after sorting by profit density `p_i / w_i`. The LP relaxation bound is typically very tight — often within 1–2% of the optimum — making branch-and-bound with LP bounding *extremely* effective. Modern MIP solvers (Gurobi, CPLEX, HiGHS) solve instances with millions of items in seconds.

**Trade-offs:** Superb LP relaxation; scales to industrial size; less natural when additional combinatorial constraints are present.

#### Approach 3 — Dynamic Programming (DP)

Build a table `dp[c]` = best profit achievable with capacity `c`:

```
dp[0] = 0
for each item i:
    for c = W downto w_i:
        dp[c] = max(dp[c], dp[c - w_i] + p_i)

Runs in O(nW) (pseudo-polynomial). Yields exact optimal and reconstructs the solution by backtracking.

Trade-offs: Optimal and simple; pseudo-polynomial complexity (poor when W is huge or non-integer); doesn't generalise easily to side constraints.

include "globals.mzn";

int: n = 6;
int: W = 15;
array[1..n] of int: weights = [4, 6, 3, 5, 2, 7];
array[1..n] of int: profits = [7, 6, 5, 9, 4, 8];

array[1..n] of var 0..1: x;
var 0..sum(profits): total_profit;

constraint knapsack(W, weights, profits, x, total_profit);

solve maximize total_profit;

output ["Selected items: \(x)\nTotal profit: \(total_profit)\n"];

constraint sum(i in 1..n)(weights[i] * x[i]) <= W;
constraint total_profit = sum(i in 1..n)(profits[i] * x[i]);
solve maximize total_profit;

Key Techniques

1. LP Relaxation Bound (Upper Bounding)

The fractional knapsack relaxation (greedy by profit density) provides a tight upper bound. In branch-and-bound, this bound prunes branches where even the best fractional completion cannot beat the current incumbent. This is why MIP solvers are so effective here.

2. Knapsack Global Constraint (Propagation)

The knapsack global constraint propagates both ways: it infers which items must be included (their combined profit is needed to reach a lower bound) and which cannot be included (their weight would bust the capacity even without other mandatory items). This dual inference is far stronger than applying a weight-sum constraint and a profit-sum constraint separately.

3. Symmetry Breaking & Dominance

If two items have w_i ≤ w_j and p_i ≥ p_j, item j is dominated and can be pruned before solving. Similarly, cover inequalities — cuts that say "you can't take all items in a minimal infeasible set" — are used by MIP solvers to dramatically tighten the LP relaxation.

Challenge Corner

Extension: The multi-dimensional knapsack (MKP) adds m resource constraints:
∑ w_{ij} · x_i ≤ W_j for each resource j ∈ {1..m}.
The LP relaxation becomes much weaker as m grows, making this NP-hard in a much more practical sense.

Can you model the MKP in CP and identify which propagation guarantees are lost compared to the 1D case? What heuristics would you use to guide search when the LP bound is weak?

References

1. Pisinger, D. & Toth, P. (1990). Knapsack Problems. Springer. — The definitive reference; covers all variants, algorithms, and complexity.
2. Kellerer, H., Pferschy, U. & Pisinger, D. (2004). Knapsack Problems. Springer. — Comprehensive modern treatment including multi-dimensional and multiple knapsack variants.
3. Trick, M. (2003). [A tutorial on integer programming]((mat.gsia.cmu.edu/redacted) — Approachable introduction connecting DP, LP relaxation, and branch-and-bound for knapsack-type problems.
4. OR-Tools CP-SAT documentation — [Knapsack example]((developers.google.com/redacted) — Shows practical CP and MIP modeling with the knapsack_solver and CP-SAT APIs side by side.

Generated by Constraint Solving — Problem of the Day · ● 175.6K · ◷

• expires on Apr 12, 2026, 12:54 PM UTC