Why spreading a load can reduce cost
Suppose a fixed workload must be distributed among several stations. Assigning every unit to one station may create a high congestion cost, so spreading the load can help. As a tractable model, let each station's cost grow quadratically in its own workload.
Definition 8.6.1
(Quadratic allocation problem)
Let be a fixed workload, the number of stations, and known coefficients. An allocation is a vector with and . The problem is
Write . A larger means that station absorbs load more cheaply.
The model is continuous: fractional workloads are allowed. It has no station capacity, fixed activation charge or uncertainty. Those omissions are assumptions, not properties of every allocation problem.
Find a candidate from equal marginal costs
For a positive allocation at station , the derivative of its cost is . If two positive stations have different marginal costs, moving a sufficiently small amount from the higher-marginal-cost station to the lower one decreases the total cost. This motivates setting for all . The equality constraint then gives and the candidate
For every coordinate is positive; for the candidate is the zero vector.
Common mistake
(Mistaking the exchange argument for a proof)
The exchange argument shows only that an allocation in which two positive stations have different marginal costs can be improved. It assumes that some minimizer exists, and it says nothing directly about allocations with zero coordinates. It proposes the candidate; a global argument, such as the identity below, is still needed to show that no other feasible allocation is better.
Theorem 8.6.2
(Proportional allocation is optimal)
In the quadratic allocation problem, with is the unique global minimizer, and the minimum cost is . More precisely, every real vector with satisfies
Proof
(Completing the square around the candidate)
For any with , write . Both vectors sum to , so . Since for every , expanding yields
Also , which gives the displayed identity. All are strictly positive, so equality holds exactly when every . The candidate has nonnegative coordinates and sums to , so it is feasible and is therefore the unique global minimizer. This proof includes and does not require guessing a local minimum or assuming a solution exists in advance.
Proof X-ray
Where each hypothesis enters
The key move is the choice of expansion point. Because the ratio is the same number at every station, the linear term collapses to , and the sum constraint makes it vanish. Expanding around an allocation with unequal ratios would leave a linear term that is negative for some admissible . Strict positivity of every is used twice: it makes each square term nonnegative, and it makes equality force , which is the uniqueness claim. The constraint is never used in the identity; it matters only when checking that itself is feasible, which holds because . No existence theorem is needed, since every feasible point is compared with directly.
Worked allocations
Worked example 8.6.3
(Two stations and an equal split)
Let , , and . Then and . Its cost is . The marginal costs are both two. For comparison, allocation costs , larger than six. The difference is exactly , as predicted by the identity.
Counterexample mode
Equal workloads need not minimize cost
Equal allocation in this example is feasible but not optimal: the stations have different coefficients . At the optimum their marginal costs are equal, not necessarily their workloads. If all were equal, the formula would instead give equal workloads.
The identity also handles a modified feasible set, provided the modified set is searched explicitly.
Worked example 8.6.4
(A binding capacity breaks equal marginal costs)
Keep and , and add the capacity . The proportional candidate is now infeasible. Every allocation has the form , so and the identity gives
On this decreases as increases, so the optimum is with cost . Directly, . The marginal costs are and : the capped station would like more load but cannot take it, so the equal-marginal-cost condition fails at the constrained optimum.
Worked example 8.6.5
(Three stations and the value formula)
Let and , so and . The cost is , which equals . Moving from station 3 to station 1 gives and changes the cost by
in agreement with . The first-order terms cancel exactly because the marginal costs and are equal. In the degenerate case the only allocation is , and the formula gives the same point with .
Limits and interpretation
The value at the optimum is . Increasing changes that value quadratically under this exact model. If individual upper capacities are added, the proportional candidate may violate a capacity and cannot simply be used; for example excludes . Fixed costs, integer workloads, or a different objective also change the problem. Equal marginal costs need not hold between a station at a binding capacity and one away from it.
Exercises
Quick check
(For and , find the optimal allocation and cost.)
Solution · Answer
, so and cost is , which equals .
Quick check
(With and , calculate the cost gap of from the optimum using the square formula.)
Solution · Answer
Here , so the gap is .
Quick check
(What is the only feasible allocation when ? Does the formula give it?)
Solution · Answer
Nonnegative coordinates summing to zero must all be zero; the formula gives the zero vector.
Quick check
(Why does an upper bound invalidate as a solution to the modified example?)
Solution · Answer
It violates . A proof for the original feasible set does not make an infeasible point valid for a modified problem.