Knapsack Model

This post applies Declarative Differential Models (DDM) to the classic knapsack optimization problem—showing how continuous simulation can replace traditional combinatorial search.

Problem Definition

Items:
  Name    Weight  Value  Efficiency (v/w)
  ------  ------  -----  -----------------
  item0        2     10               5.00
  item1        4     10               2.50
  item2        6     12               2.00
  item3        9     18               2.00

Capacity: 15

Optimal solution: items 0, 1, 3 → weight=15, value=38

The Model

The Petri net represents the knapsack as a dynamic system:

Item places: 1 token = available, 0 = taken (enforces 0/1 constraint)
Capacity place: Holds tokens representing available weight budget
Take transitions: Consume item + capacity, produce value + weight tracking

Using pflow.xyz, we can model and run ODE analysis directly in the browser.

Mass-Action Dynamics

Items compete for limited capacity via mass-action kinetics:

flux = rate × [item] × [capacity]

Arc weights determine consumption amounts. All items are taken proportionally based on availability—high-value items don't automatically win; the dynamics emerge from the structure.

ODE Simulation Results

Running mass-action kinetics with uniform rates:

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 continuous relaxation takes fractional amounts of each item—all equally at 71.4%. This is the nature of ODE simulation: it finds a smooth approximation rather than discrete 0/1 choices.

Exclusion Analysis

Disabling each item's transition reveals its contribution:

Excluded	Final Value	Relative
none	35.71	100.0%
item0	31.58	88.4%
item1	35.29	98.8%
item2	37.75	105.7%
item3	32.00	89.6%

Key insights:

item0 has highest impact when excluded (88.4%) — makes sense, it's the most efficient (v/w = 5.0)
item2 exclusion improves value (105.7%) — it's competing for capacity better used elsewhere
item3 second-highest impact (89.6%) — high absolute value despite lower efficiency

Data generated with go-pflow examples/knapsack

Convergence to Optimal

When the suboptimal item (item2) is excluded, the ODE converges to the discrete optimal:

Time	Value	Gap to Optimal
t=10	37.75	0.2517
t=100	37.97	0.0253
t=1000	38.00	0.0025

The continuous relaxation finds the optimum through dynamics rather than combinatorial search.

Comparison: Branch-and-Bound

For exact solutions, branch-and-bound systematically explores all possibilities:

Discrete optimal: Pick items 0,1,3 → value=38
ODE approximation: Continuous relaxation ≈ 35.71

With exclusion analysis, the ODE approach recovers the exact solution. The insight: item2 competes for capacity that's better allocated to items 0, 1, and 3.

When to Use Each

DDM/ODE Approach	Branch-and-Bound
Exploratory analysis	Exact solutions
Sensitivity insights	Guaranteed optimum
Fast iteration	Higher implementation cost
Visualize dynamics	Deterministic results

Conclusion

DDM transforms optimization from search into simulation. The continuous relaxation trades exactness for insight—showing how items compete, which matter most, and how the system behaves under constraints.

For more on DDM theory and how-to: Declarative Differential Models