Allocate a budget to maximize return in Python

Resource allocation — splitting a fixed budget, headcount, or capacity across competing options to get the most out of it — is one of the most common optimization problems in day-to-day code: allocate marketing spend across channels, capital across projects, compute across jobs. With quicopt it is a short linear program (LP) in Python.

Real allocations are rarely limited by money alone. Here each channel also costs management hours, and the team only has so many — and the highest-return channel is by far the most hours-hungry. Two scarce resources, and the choices stop being independent.

The naive approach

Without the vocabulary, the instinct is to pour money into the highest-return channel first, then the next:

ret   = [0.12, 0.10, 0.15, 0.08]   # return per unit spent
hours = [1.0,  1.0,  4.0,  1.0]    # management hours per unit spent
cap   = [40.0, 50.0, 30.0, 60.0]   # max spend per channel
budget, team_hours = 100.0, 160.0

spend = [0.0] * len(ret)
for i in sorted(range(len(ret)), key=lambda i: -ret[i]):
    take = min(cap[i], budget, team_hours / hours[i])
    spend[i] = take
    budget -= take
    team_hours -= take * hours[i]

print("return:", sum(ret[i] * spend[i] for i in range(len(ret))))  # -> 9.3

Greedy spends 40 on channel 0 and 30 on channel 2 and returns 9.3. It walked into the trap: channel 2 has the best return per euro, but at 4 hours per unit it burns 120 of the 160 team hours. The hours run out, and €30 of the budget is left unspendable. The best return per euro is not the best return per hour, and with two limits you cannot rank channels on one number at all.

Sorting by return-per-hour instead just moves the trap; grid-searching the splits explodes with the number of channels. The problem is continuous and linear — so model it and solve it exactly.

Model it as an LP

Each channel gets a continuous variable spend[i] bounded by its cap. Two constraints — one per scarce resource — and the objective maximizes total return:

from ortools.math_opt.python import mathopt
from quicopt import Client

# Allocate a fixed budget across channels to maximize return. Each channel has a
# per-unit return, a spend cap, AND a management-hours cost per unit spent — and
# the team has a limited number of hours. Two scarce resources (budget + hours),
# so pouring money into the highest-return channel first is NOT optimal.
ret   = [0.12, 0.10, 0.15, 0.08]   # return per unit spent
hours = [1.0,  1.0,  4.0,  1.0]    # management hours needed per unit spent
cap   = [40.0, 50.0, 30.0, 60.0]   # max spend per channel
budget     = 100.0
team_hours = 160.0
N = len(ret)

model = mathopt.Model(name="resource_allocation")
x = [model.add_variable(lb=0.0, ub=cap[i], name=f"spend_{i}") for i in range(N)]
model.add_linear_constraint(sum(x) <= budget)
model.add_linear_constraint(sum(hours[i] * x[i] for i in range(N)) <= team_hours)
model.maximize(sum(ret[i] * x[i] for i in range(N)))

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
print(client.solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  11.8
├── x:          spend_0=40, spend_1=40, spend_2=20, spend_3=0  (4 variables)
└── solve_time: 0.4199 s

What you get

status: optimal means the split is proven best — return 11.8, against greedy's 9.3. That is 27% more return from the same budget and the same team, and it comes from a split no ranking rule would produce: the solver holds back on the highest-return channel (20 instead of its 30 cap) and puts the freed hours into channel 1, which greedy skipped entirely. Every euro and every hour gets used.

That is the difference between a heuristic and a solver. Greedy commits to one resource's ranking and cannot see the trade; the LP prices both resources at once and proves there is nothing better.

Because it is an LP, the same model scales from four options to four thousand, and from two scarce resources to twenty — you change the data, not the method.

Next

• The problem class behind this: Linear programming (LP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.