← Home
knapsack optimization petri-net ode ddm

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:

pflow

Problem Definition

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

Item Efficiency

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.

The Model

Model Structure

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.

Mass-Action Dynamics

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.

ODE Simulation Results

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.

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. The example's README carries the same closed form and the same two tables. No test pins these numbers: the example only prints them.

Exclusion Analysis

Exclusion Analysis

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

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:

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.

Comparison: Branch-and-Bound

Branch-and-Bound vs DDM/ODE

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.

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 printed different item0 and item1 exclusion rows at the time (33.81 and 37.75), which disagreed with the formula; it has since been corrected and now matches the values here.
  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.
  4. Where the 38 comes from (October 2026). The example prints it as a constant, so the post now enumerates the subsets. The sentence saying branch-and-bound "finds" it implied a run nobody made and is gone. Chapter 8 now uses this same instance, so "a variant" came out, and "usually drops several items" became "can", since nothing here measures how often.

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

×

Follow on Mastodon