Yes. Mixed-integer programming (MIP) is a standard way to allocate limited resources when some decisions are yes/no or whole numbers: fund this project or not, open this site or not, assign this person to that shift. You write the goal (maximize value), the limits (budget, headcount) and mark those decisions as integer; a solver finds the best allocation.
It earns its place over a simple ranking when the limits interact. In the example below, picking projects by value per dollar returns 120; the optimal allocation returns 130.
The Problem
This is a small illustrative example. You have a budget of 80 (in any unit) and five candidate projects. Each is all-or-nothing: you fund it fully or not at all.
| Project | Cost | Value | Value per cost |
|---|---|---|---|
| A | 40 | 70 | 1.75 |
| B | 30 | 50 | 1.67 |
| C | 25 | 38 | 1.52 |
| D | 20 | 30 | 1.50 |
| E | 15 | 22 | 1.47 |
Why Ranking by Value per Cost Falls Short
The obvious shortcut is to take projects in order of value per cost until the money runs out. That picks A (40) then B (30), spends 70 and cannot fit C, D or E in the remaining 10. Total value: 70 + 50 = 120.
The best feasible choice is A + C + E: cost 40 + 25 + 15 = 80, value 70 + 38 + 22 = 130. The shortcut ignores that leaving 10 unspent is wasteful, and that is the kind of interaction an integer program handles by looking at combinations rather than one project at a time.
| Method | Projects funded | Cost | Value |
|---|---|---|---|
| Rank by value per cost | A, B | 70 | 120 |
| Optimal (integer program) | A, C, E | 80 | 130 |
| Relaxed version (fractions allowed) | A, B and a fraction of C | 80 | 135.2 (an upper bound, not a feasible plan) |
The relaxed value is useful as a bound: no all-or-nothing plan can beat 135.2, so the 130 solution is within about 4% of the best that is theoretically possible.
The Model
Let x_i be 1 if project i is funded and 0 if not.
- Maximize the sum of
value_i * x_i - Subject to the sum of
cost_i * x_i <= 80 - With each
x_ian integer between 0 and 1
Solving It in Python
import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds
cost = np.array([40, 30, 25, 20, 15])
value = np.array([70, 50, 38, 30, 22])
res = milp(
c=-value, # milp minimizes, so negate value
constraints=LinearConstraint(cost[None, :], ub=80),
integrality=np.ones(5), # 1 = integer; with bounds 0..1 = yes/no
bounds=Bounds(0, 1),
)
print(res.x.round(), -res.fun) # [1. 0. 1. 0. 1.] 130.0The output selects projects A, C and E for a value of 130. scipy.optimize.milp is available in SciPy 1.9 and later; PuLP, OR-Tools and commercial solvers use the same model shape.
Other Resource Allocation Problems That Fit
- Several resources at once. Add one constraint per resource (budget, engineer-weeks, floor space).
- Dependencies. "Fund B only if A is funded" becomes
x_B <= x_A. - Either-or choices. "At most one of C and D" becomes
x_C + x_D <= 1. - Locations and assignments. Which sites to open, which technician covers which route.
Limits to Know
- The answer is only as good as the value estimates. Garbage-in numbers produce a precise-looking wrong plan.
- Solve time can grow quickly with problem size and tangled constraints; most business-scale models still solve in seconds to minutes.
- If every decision can be fractional (budget split across channels, say), you do not need integers: plain linear programming is simpler and faster.
For the wider method, see integer programming.
Frequently Asked Questions
Can I use mixed-integer programming for resource allocation?
Yes. It is a standard method when some decisions are all-or-nothing or whole numbers, such as which projects to fund, which sites to open or which staff to assign, and the resources are limited.
What is the difference between linear programming and integer programming?
Linear programming lets decisions take any fractional value. Integer programming requires some or all decisions to be whole numbers, often 0 or 1 for no or yes. Integer problems are harder to solve but match all-or-nothing choices.
Why not just rank options by value per cost?
Ranking works only when you can fund fractions of options. With all-or-nothing choices, the top-ranked options can leave budget unspent that a different combination would use. In the example above, ranking returns 120 and the optimal combination returns 130.
What software solves mixed-integer programs?
In Python, scipy.optimize.milp (SciPy 1.9 and later), PuLP and OR-Tools are common free options; commercial solvers are also widely used for large models.
How do I model 'fund B only if A is funded'?
With yes/no variables x_A and x_B, add the constraint x_B <= x_A. If A is not funded (x_A = 0), B is forced to 0.