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:
Four items and a weight capacity of 15:
| Item | Weight | Value | Value/weight |
|---|---|---|---|
| item0 | 2 | 10 | 5.00 |
| item1 | 4 | 10 | 2.50 |
| item2 | 6 | 12 | 2.00 |
| item3 | 9 | 18 | 2.00 |
The optimal solution picks items 0, 1 and 3 — exactly 15 units of capacity for a total value of 38. The example prints that as a string constant and never computes it, so here is the check by hand: of the sixteen subsets, three are over capacity ({0,2,3} at 17, {1,2,3} at 19, all four at 21), and of the thirteen that fit the best is {0,1,3} at 38, then {0,1,2} at 32. 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.
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. The live model runs the ODE analysis in the browser, and the same places, arcs and weights are checked into go-pflow as a parse golden if you would rather read them than click through them.
go-pflow's rate law is first-order in every input place (buildVecODEFunction in solver/ode.go; the browser solver, petri-solver.js, multiplies by the same first powers), 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.
Output of the example at t = 10 (cd examples/knapsack/cmd && go run main.go):
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.
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. The example's README carries the same closed form and the same two tables. No test pins these numbers: the example only prints them.
Disabling one item at a time (its token and rate set to 0) and running to t = 10:
| Excluded | Active W | Active V | Closed form | Final Value | Relative |
|---|---|---|---|---|---|
| none | 21 | 50 | 15·50/21 | 35.71 | 100.0% |
| item0 | 19 | 40 | 15·40/19 | 31.58 | 88.4% |
| item1 | 17 | 40 | 15·40/17 | 35.29 | 98.8% |
| item2 | 15 | 38 | → 38 | 37.75 | 105.7% |
| item3 | 12 | 32 | 32 | 32.00 | 89.6% |
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.
If you run the example, its closing printout disagrees with this table in one place. It says the most valuable items cause the biggest drop and names item3, which does have the largest value at 18, but item0, at value 10, drops further. The table is the measurement, and the printout's gloss on it is wrong.
Data generated with go-pflow examples/knapsack
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:
| Time | Value | Gap to Optimal |
|---|---|---|
| t=10 | 37.75 | 0.2517 |
| t=100 | 37.97 | 0.0253 |
| t=1000 | 38.00 | 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.
Branch-and-bound treats optimization as search: a decision tree where each node is a take-or-skip choice, with upper bounds pruning the branches that can't beat the best solution found so far. That is exponential in the worst case and practical at moderate sizes. The ODE treats it as simulation, with no decisions anywhere; items compete for capacity through the mass-action kinetics above, 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.
| Aspect | Branch-and-Bound | DDM/ODE |
|---|---|---|
| Core operation | Decision-tree search with bounds | One ODE integration per run |
| Decisions | Explicit (take/skip) | None — every active item is taken in the same fraction |
| Solution type | Exact integer optimum | Fractional; 35.71 here against 38 |
| Cost | Exponential worst case, pruned | One ODE solve per run; exclusion analysis is n + 1 runs |
| What it tells you | The optimum | How value density and fit shift when items are removed |
We have not run a branch-and-bound on this instance. The link is a general write-up of the method, go-pflow has no implementation, and the 38 comes from the enumeration above, which any exact method has to agree with. The figure's tree is a sketch rather than a trace of a run, and its item0 bar is drawn longer than the others though all four are 71.4%. On this instance one round of single-item exclusions — five ODE runs — also points at the optimum: 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 can drop 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 instance and closed form are worked through in Chapter 8: Optimization of Petri Nets as a Universal Abstraction.
For readers of the earlier version:
Related: Declarative Differential Models · The Incidence Reduction · The Capacity Paradox