Municipal Budget Allocation

0-1 Knapsack · Dynamic Programming / Greedy

A city council must select which of 10 public improvement projects to fund from a $30M annual capital budget. Each project has an estimated social benefit score (1–10) and cost ($1–8M). Optimal allocation can deliver 30–50% more public value than ad-hoc political selection.

Infrastructure Service Scheduling Emergency Resource Allocation

The Problem

Maximizing social benefit under a capital budget constraint

A municipality evaluates 10 candidate public improvement projects, each with an estimated social benefit score (on a 1–10 scale) and a corresponding capital cost ranging from $1M to $8M. The annual capital budget is constrained — the city cannot fund every proposal. The objective is to select the subset of projects that maximizes total social benefit without exceeding the available budget.

This maps directly to the 0-1 Knapsack Problem: each project is an item with a value (benefit score) and a weight (cost in $M), and the knapsack capacity is the city’s budget. The binary decision variable for each project — fund or defer — makes this a combinatorial optimization problem. While NP-hard in general, the problem admits efficient exact solutions via dynamic programming when costs are discretized.

0-1 Knapsack Formulation maximize Σ_i=1..n b_i x_i // total social benefit of funded projects
subject to
Σ_i=1..n c_i x_i ≤ B // capital budget constraint
x_i ∈ {0, 1} // fund (1) or defer (0) each project

Where b_i is the benefit score of project i, c_i is the capital cost, B is the total capital budget, and x_i is the binary decision variable.

See full 0-1 Knapsack theory and all algorithms

Try It Yourself

Select public projects to maximize social benefit within budget

Budget Optimizer

10 Projects · Budget $30M

Scenario

Annual Capital Budget

$30M

Total Benefit Score 0

Budget Utilization $0M / $30M

Candidate Projects — click to toggle

Allocation Visualization

Ready. Click “Solve & Compare All Algorithms” to run.

Algorithm Comparison

Algorithm	Benefit	Projects	Budget Used	Time
Click Solve & Compare All Algorithms

Solution Detail

Solution details will appear here after solving.

Business Impact

—

Budget Cycle Frequency

—

Population Served

The Algorithms

Exact, heuristic, and randomized approaches to the 0-1 Knapsack

Heuristic

Greedy by Benefit/Cost Ratio

O(n log n)

Sort all projects by their benefit-to-cost ratio (social benefit per dollar of capital) in descending order. Greedily add projects to the funded set as long as the budget is not exceeded. This combined greedy (best of density-first and max-value-first) guarantees at least 50% of OPT and runs in O(n log n) time. Often produces near-optimal solutions for municipal budgets.

Exact

Dynamic Programming

O(nB) | Pseudo-polynomial

Build a table of dimension n × B, where each cell stores the maximum benefit achievable using the first i projects with budget b. For each project, choose the better of excluding it (inherit the row above) or including it (add its benefit to the best solution at reduced budget). Backtrack through the table to recover which projects are funded. Guarantees an optimal solution but memory and time scale with the budget magnitude.

Baseline

Random Selection

O(n)

Randomly shuffle all projects and greedily add them in the shuffled order until the budget is exhausted. This serves as a baseline comparator representing ad-hoc, non-systematic allocation. Run multiple trials and take the best result to see how random selection compares to structured optimization. Typically achieves 40–70% of OPT.

Real-World Complexity

Why municipal budget allocation goes beyond the classic knapsack

Beyond One Constraint

Multi-year capital plans — Projects span multiple fiscal years; a time-phased budget model replaces a single capacity constraint
Geographic equity — Wards and districts demand proportional spending, adding fairness constraints to pure benefit maximization
Mandatory projects — Regulatory compliance (e.g., water safety) forces certain items in, reducing effective budget for discretionary selection
Project dependencies — Some projects require others as prerequisites (e.g., water main before road repaving), introducing precedence constraints
Political and social factors — Stakeholder preferences, electoral cycles, and community input add non-quantifiable dimensions to the decision
Uncertainty in costs — Construction overruns and contingency reserves turn deterministic costs into stochastic variables
Synergy effects — Co-locating infrastructure upgrades (e.g., sidewalk + lighting) reduces mobilization costs but complicates the objective function

Key References

Foundational works in knapsack optimization and public resource allocation

Kellerer, H., Pferschy, U. & Pisinger, D. (2004). “Knapsack Problems.” Springer.
Dantzig, G. B. (1957). “Discrete-variable extremum problems.” Operations Research, 5(2), 266–288.
Figueira, J., Greco, S. & Ehrgott, M. (2005). “Multiple Criteria Decision Analysis: State of the Art Surveys.” Springer.
Martello, S. & Toth, P. (1990). “Knapsack Problems: Algorithms and Computer Implementations.” Wiley.

Need to optimize your public budget?

From capital allocation to multi-criteria project ranking and equity-constrained optimization, mathematical modeling can transform how municipalities allocate resources. Let’s discuss how Operations Research can work for your community.

Connect on LinkedIn

Disclaimer

Data shown is illustrative. Project names, benefit scores, and capital costs are representative scenarios for educational purposes and do not reflect any specific municipality or budget.