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

Given four items with different weights and values, we must select a subset that maximizes total value while staying within a weight capacity of 15. The efficiency ratio (value/weight) reveals item0 as the clear winner at 5.0, while item2 and item3 tie at 2.0 despite different absolute values.

The optimal solution picks items 0, 1, and 3—using exactly 15 units of capacity for a total value of 38. Notably, item2 is excluded despite having reasonable efficiency because its weight (6) prevents the higher-value item3 (weight 9) from fitting.

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:

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:

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

Comparison: Branch-and-Bound

The two approaches solve the same problem through fundamentally different mechanisms.

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

DDM/ODE treats optimization as simulation. Instead of explicit decisions, items compete for capacity through continuous dynamics. The mass-action kinetics flux = rate × [item] × [capacity] means all enabled transitions fire simultaneously at rates proportional to available resources. There's no decision tree—just differential equations evolving toward equilibrium.

For exact solutions, branch-and-bound finds items 0, 1, 3 → value=38. The ODE relaxation reaches ≈35.71 by taking fractional amounts of everything.

But the ODE reveals structure that search obscures. Exclusion analysis shows item2 actively hurts the solution—it's not just "not selected," it's competing for capacity better used elsewhere. This insight guides us to the discrete optimum without exhaustive search.

When to Use Each

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