Knapsack Model

We apply Declarative Differential Models (DDM) to a four-item 0/1 knapsack and compare what the continuous relaxation finds against the exact answer. The model is the one in go-pflow's examples/knapsack, and the same net is live on pflow.xyz:

Problem Definition

Four items and a weight capacity of 15:

The optimal solution picks items 0, 1 and 3 — exactly 15 units of capacity for a total value of 38. Item2 and item3 tie on efficiency at 2.0, so the ratio can't choose between them; capacity does. Once items 0 and 1 have taken 6 units, item3 fills the remaining 9 exactly, while item2 would leave 3 idle (items 0, 1, 2 weigh 12 and are worth 32).

The Model

Each item is a place holding a single token, which is where the 0/1 constraint lives: there is only one of it to take. A shared capacity place starts with 15 tokens. Each take transition consumes its item's token and w tokens of capacity, and produces v tokens in a value place and w in a weight place. Using pflow.xyz, the ODE analysis runs directly in the browser.

Mass-Action Dynamics

go-pflow's rate law is first-order in every input place (solver/ode.go), so each take transition fires at

flux = rate × [item] × [capacity]

Arc weights scale how much is consumed and produced, not the rate. Every transition runs at rate 1.0.

ODE Simulation Results

Output of the example at t = 10:

Final state (continuous approximation):
  Value accumulated:    35.71
  Weight used:          15.00
  Capacity remaining:    0.00

Item consumption (fraction taken):
  item0: 71.4% taken
  item1: 71.4% taken
  item2: 71.4% taken
  item3: 71.4% taken

The relaxation takes the same fraction of every item — the dense item0 and the bulky item3 alike — and that fraction is exact, not an artifact of the integrator.

Why Every Item Stops at 71.4%

The rate law makes this solvable by hand. Write τ(t) for the integral of capacity from 0 to t. Each item place obeys d[item]/dt = −[item]·[capacity], so [item] = e^(−τ) — the same function for every item, whatever its weight or value. Values never enter the dynamics at all; they sit on output arcs into a place nothing reads. So all active items are taken in one common fraction f = 1 − e^(−τ), and capacity is 15 − W·f, where W is the total weight of the items still in play. If W > 15, capacity runs out when f = 15/W and the net settles at value 15·V/W. If W ≤ 15, f climbs toward 1 and the net eventually collects all of V.

With all four items, W = 21 and V = 50: f = 15/21 = 71.4%, value 750/21 = 35.71. The numbers in the output above and in both tables below follow from this formula. We derived it from the rate law and checked it against the published figures; the example itself was not re-run for this revision.

Exclusion Analysis

Disabling one item at a time (its token and rate set to 0) and running to t = 10:

Read through the formula, the table ranks subsets by value density V/W, scaled by capacity, until a subset fits. Dropping item0 costs the most because it is the densest item: without it V/W falls from 2.38 to 2.11. Dropping item3 lands at 89.6% for a different reason — the remaining three weigh 12, so they fit, and the net collects their full 32 with 3 units of capacity unused. Item2 is the only item whose removal raises the value, because without it the remaining weights sum to exactly 15 and the net can take all of items 0, 1 and 3. Calling item2 "harmful" is fair in that sense and no stronger one: its exclusion is the one that makes the rest fit.

Data generated with go-pflow examples/knapsack

Convergence to Optimal

With item2 excluded, W equals the capacity, so capacity and items drain together: [capacity] = 15·e^(−τ), which integrates to e^τ = 1 + 15t. The value is 38·(1 − 1/(1 + 15t)) and the gap to 38 is 38/(1 + 15t) — algebraic, not exponential, which is why it takes until t = 1000 to get within 0.0025:

The ODE reaches the discrete optimum here because 2 + 4 + 9 = 15; the dynamics don't select that subset, they fill it once it is the only one left.

Comparison: Branch-and-Bound

Branch-and-bound treats optimization as search. It builds a decision tree where each node is a binary choice — take this item or skip it — and computes upper bounds to prune branches that can't beat the best solution found so far. It's systematic enumeration with pruning: exponential in the worst case, practical for moderate problem sizes.

DDM/ODE treats optimization as simulation. There are no explicit decisions; items compete for capacity through the mass-action kinetics above, with every enabled transition firing at once at a rate proportional to what's available. It is also not the LP relaxation of the knapsack. The LP optimum here is 38 — take items 0 and 1 whole, then fill the last 9 units at ratio 2.0 — and an LP bound sits at or above the integer optimum, while the ODE settles at 35.71, below it, because it spreads capacity evenly across items instead of maximizing anything.

For exact solutions, branch-and-bound finds items 0, 1, 3 → value 38. On this instance one round of single-item exclusions — five ODE runs — also points at it: drop item2 and what's left is the answer. We have not shown that this works in general. Single exclusions only look at subsets of size n − 1, the optimum on a larger instance usually drops several items, and nothing here says an iterated version finds it. A benchmark of exclusion analysis against branch-and-bound on larger instances is the worked case this post still owes.

The same approach is worked through in Chapter 8: Optimization of Petri Nets as a Universal Abstraction, on a variant of this instance.

What Changed

For readers of the earlier version:

1. Efficiencies. item1 is 10/4 = 2.50 and item3 is 18/9 = 2.00, matching the code, the pflow.xyz model and the figure; the text had said 2.33 and 1.78. With item2 and item3 tied at 2.0, item3 wins on fit, not efficiency.
2. Closed form. Added the derivation: every active item is taken in the same fraction, and the value is 15·V/W while W > 15. Every number in the tables matches it. The go-pflow example's README prints different item0 and item1 exclusion rows (33.81 and 37.75); those disagree with the formula, and the post keeps the values the formula gives.
3. Claims narrowed. The ODE is not the LP relaxation (the LP gives 38 here); convergence with item2 excluded happens because the remaining weights sum to the capacity; exclusion analysis finding the optimum is shown for this instance only. Dropped the "When to Use Each" table, which listed "deterministic results" as a branch-and-bound advantage — the ODE is deterministic too.

Related: Declarative Differential Models · The Incidence Reduction · The Capacity Paradox