Linear Programming

What linear programming helps decide

In health economics, it can allocate budgets, workforce, beds, appointments, medicines or service capacity across competing uses. This page explains the mathematical structure, shows how an allocation problem is solved and interpreted, and identifies when integer decisions, uncertainty or non-linear relationships require an extension.

A linear programme does not decide what a health system ought to value. It optimises the objective supplied by the analyst within the stated constraints, so omitted objectives, weak evidence or poorly specified constraints can produce an efficient mathematical answer to the wrong policy question.

The model has decisions, an objective and constraints

Every linear programme contains decision variables, an objective function and constraints. The decision variables are the quantities the optimiser may change, the objective states what should be maximised or minimised, and the constraints define which combinations are feasible. All coefficients are fixed within one deterministic run.

A standard maximisation problem is:

$$\max_{x}\; z=c^{\mathsf T}x$$

subject to:

$$Ax\le b$$ $$x\ge0$$

where:

• (x) is the vector of decision variables.
• (c) is the vector of contribution to the objective per unit of each decision.
• (A) is the matrix of resource use or other constraint coefficients.
• (b) is the vector of available resources or limits.
• (z) is the optimised objective value.

Linearity imposes specific assumptions

Linear programming assumes that each additional unit contributes a constant amount to the objective and consumes a constant amount of each constrained resource. It also assumes that contributions add across decisions and that no interaction changes the value of a combination. These assumptions make the problem tractable but may not represent economies of scale, congestion, thresholds or changing treatment effectiveness.

The main assumptions are:

• Proportionality means that doubling a decision doubles its objective contribution and resource use.
• Additivity means that total benefit and resource use equal the sum of the contributions from individual decisions.
• Divisibility means that decision variables may take fractional values unless integrality is imposed.
• Certainty means that coefficients are treated as known within the optimisation run.
• Non-negativity means that ordinary activity levels cannot fall below zero unless a variable is explicitly reformulated.

An assumption can be mathematically convenient without being decision-appropriate. The analyst should test whether the feasible operating range is narrow enough for a linear approximation to remain credible.

A worked health-service allocation problem

Suppose a commissioner can fund two programmes, (A) and (B). Each programme produces expected health gain but uses a limited budget and limited clinical time. The objective is to maximise total QALYs while respecting both constraints.

Let:

• (x_A) be the number of patients assigned to programme (A).
• (x_B) be the number of patients assigned to programme (B).
• Programme (A) produces 0.40 QALYs, costs £2,000 and uses 3 clinical hours per patient.
• Programme (B) produces 0.25 QALYs, costs £1,000 and uses 2 clinical hours per patient.
• The available budget is £100,000 and clinical capacity is 240 hours.

The linear programme is:

$$\max\; z=0.40x_A+0.25x_B$$

subject to:

$$2{,}000x_A+1{,}000x_B\le100{,}000$$ $$3x_A+2x_B\le240$$ $$x_A,x_B\ge0$$

The budget constraint can be simplified to (2x_A+x_B\le100). At the intersection of the budget and capacity boundaries:

$$2x_A+x_B=100$$ $$3x_A+2x_B=240$$

Solving gives:

$$x_A=40,\qquad x_B=20$$

The objective value is:

$$z=(0.40\times40)+(0.25\times20)=21\;\text{QALYs}$$

The allocation uses the full £100,000 budget and all 240 clinical hours. The solution is optimal for the stated coefficients and constraints, but it does not account for uncertainty, indivisible programme setup, equity priorities or patients' eligibility unless those features are added explicitly.

The feasible region contains every allowable allocation

Each constraint removes combinations of decisions that violate a resource or policy limit. The remaining set of allocations is the feasible region. If the feasible region is non-empty and the objective has a finite optimum, a linear programme reaches an optimum at an extreme point, although several extreme points or an entire boundary may share the same objective value.

Important solution states include:

• A feasible optimal solution satisfies every constraint and has the best attainable objective value.
• Multiple optima occur when more than one feasible allocation achieves the same objective value.
• Infeasibility occurs when no allocation can satisfy all constraints simultaneously.
• Unboundedness occurs when the objective can improve without limit because a necessary constraint is absent.
• Degeneracy occurs when more constraints are binding at a solution than are needed to locate it, which can affect numerical solution paths and sensitivity interpretation.

An infeasible or unbounded result is usually a model-specification signal rather than a solver failure. The analyst should inspect constraint logic, units, bounds and omitted resource limits before changing solver settings.

Binding constraints determine the immediate bottlenecks

A binding constraint is exactly met at the solution, while a non-binding constraint has unused capacity, called slack. Binding constraints identify the resource limits that prevent further improvement under the current model. A non-binding constraint can still be operationally important, but a small increase in its right-hand side does not improve the objective locally.

For a resource constraint (a_j^{\mathsf T}x\le b_j), slack is:

$$s_j=b_j-a_j^{\mathsf T}x$$

At the worked solution, both budget and clinical capacity have zero slack. If only 220 of 240 clinical hours were used, the capacity constraint would have 20 hours of slack and would not be the immediate limiting resource.

Shadow prices value one more unit of a constrained resource

The shadow price, or dual value, measures the change in the optimal objective from a one-unit increase in a constraint's right-hand side, within a range where the current solution structure remains valid. It expresses the marginal value of relaxing a binding constraint. In a QALY-maximisation model, the shadow price of budget may be interpreted as additional QALYs available from one more monetary unit under the model.

If (V(b)) is the optimal value as resource vector (b) changes, the shadow price for resource (j) is locally:

$$y_j=\frac{\partial V(b)}{\partial b_j}$$

The interpretation is conditional on the model and is not unlimited. Once the right-hand side moves far enough to change which constraints bind or which activities enter the solution, the shadow price can change.

For a maximisation problem with (Ax\le b) and (x\ge0), the associated dual can be written as:

$$\min_y\; b^{\mathsf T}y$$

subject to:

$$A^{\mathsf T}y\ge c$$ $$y\ge0$$

The dual assigns implicit values to constrained resources. Strong duality means that, when standard regularity conditions hold and optimal solutions exist, the primal and dual optimal objective values are equal.

Reduced costs show what would make an excluded activity attractive

A decision variable may be zero at the optimum because its objective contribution is insufficient relative to the resources it consumes. Its reduced cost measures how much its objective coefficient would need to improve before it could enter the solution, under the current basis and sign convention. This can help distinguish an activity that is nearly competitive from one that remains far from optimal.

For a maximisation problem, one common reduced-cost expression is:

$$\bar c_i=c_i-a_i^{\mathsf T}y$$

where (a_i) is the column of constraint coefficients for activity (i), and (y) is the vector of dual prices. Solver conventions differ, so the direction and sign should be checked against the software documentation before interpretation.

Reduced costs and shadow prices describe local sensitivity around the solution. They do not replace re-optimisation when several coefficients or bounds change together.

Integer restrictions represent indivisible decisions

Ordinary linear programming permits fractional decisions. Fractions may be meaningful for budget shares or annualised activity, but they are inappropriate for indivisible choices such as opening a clinic, buying a scanner or selecting an entire project. Integer or binary restrictions create a mixed-integer linear programme when some other variables remain continuous.

A binary decision is represented as:

$$y_i\in\{0,1\}$$

where (y_i=1) may mean that project (i) is selected. A fixed setup cost (F_i) and capacity link can be modelled using:

$$x_i\le M_i y_i$$

where (M_i) is a valid upper bound on activity. An excessively large (M_i) can weaken the numerical formulation, so it should be based on defensible capacity rather than chosen arbitrarily.

Integer programmes are not solved by rounding a continuous solution. Rounding can violate constraints or discard a better feasible combination, so the integrality conditions must be included in the optimisation itself.

Equity and access can be represented as constraints or objectives

Maximising total health alone may allocate resources away from groups with higher costs, lower treatment capacity or smaller expected gains. Equity, geographical access and minimum service guarantees can be incorporated through explicit constraints or through a multi-objective formulation. Their inclusion makes the value judgments visible rather than leaving them implicit.

Examples include:

• A minimum coverage constraint can require each region to treat at least a specified number or proportion of eligible patients.
• A maximum disparity constraint can limit differences in access between population groups.
• A protected-capacity constraint can reserve staff time or beds for a priority service.
• A distributional objective can apply explicit equity weights to health gains for selected groups.
• A lexicographic approach can optimise a primary objective and then optimise a secondary objective without worsening the primary result beyond an agreed tolerance.

These choices are normative and should not be disguised as technical adjustments. Decision makers should approve the protected groups, thresholds, weights and acceptable trade-offs.

Uncertainty requires more than one deterministic solution

The optimal allocation can change when costs, health gains, demand or capacity are uncertain. A base-case solution should therefore be accompanied by sensitivity analysis, scenario analysis or a formal optimisation method that represents uncertainty. The method should match whether uncertainty is probabilistic, bounded, sequential or adversarial.

Useful approaches include:

• Deterministic sensitivity analysis changes selected coefficients or limits and re-solves the model.
• Scenario analysis evaluates internally consistent combinations of demand, cost, benefit and capacity assumptions.
• Stochastic programming optimises expected or risk-sensitive performance across probability-weighted scenarios.
• Robust optimisation seeks solutions that remain feasible or perform acceptably across a defined uncertainty set.
• Chance-constrained programming limits the probability that a constraint will be violated.

Optimising with mean inputs is not necessarily equivalent to choosing the best decision under uncertainty. A solution that is optimal on average may have unacceptable downside risk or frequently violate capacity.

Linear programming differs from related methods

Several optimisation methods share the goal of selecting the best feasible decision but impose different mathematical structures. The distinction matters because using a linear solver does not make a non-linear or discrete problem linear. The formulation should reflect the real decision rather than the analyst's preferred software.

Common modelling and interpretation errors

An optimisation model can be solved correctly while representing the decision poorly. Most serious errors arise from omitted constraints, inconsistent units, unrealistic divisibility or an objective that does not match the policy question. The following checks should be explicit in any health-economic application.

• Maximising activity instead of value can favour high-volume services without reflecting health outcomes, costs or quality.
• Omitting a scarce resource can create an apparently optimal allocation that cannot be delivered.
• Using average coefficients outside their credible range can violate the proportionality assumption.
• Allowing fractional indivisible decisions can produce a solution that has no operational meaning.
• Double-counting benefits or resource use can distort both the objective and the constraints.
• Treating a shadow price as constant for any change ignores its allowable sensitivity range.
• Rounding continuous results after optimisation can violate feasibility or materially reduce the objective.
• Reporting one optimum without alternatives can hide multiple solutions with the same or nearly the same value.
• Ignoring uncertainty and implementation constraints can make the mathematically optimal plan fragile in practice.

A practical validation sequence

Validation should show that the equations reproduce the intended decision and that the returned solution is both feasible and optimal within the stated model. Independent calculation is especially important for the objective, resource totals and any policy constraints. The following sequence provides an auditable minimum.

1. Define every decision variable and unit and state whether it is continuous, integer or binary.
2. Trace every objective coefficient to its evidence source and confirm that benefits or costs are not double counted.
3. List every scarce resource and policy requirement and translate each one into a labelled constraint.
4. Check coefficient dimensions and units across every term in the objective and constraints.
5. Construct at least one known feasible solution before relying on the optimiser.
6. Recalculate the reported objective and constraint totals independently from the returned decision values.
7. Confirm feasibility within an explicit numerical tolerance and investigate any constraint violation.
8. Inspect binding constraints, slack, shadow prices and reduced costs using the solver's documented sign conventions.
9. Test alternative optima and near-optimal allocations to understand whether materially different plans achieve similar value.
10. Re-optimise under sensitivity and uncertainty scenarios rather than applying local sensitivity results beyond their valid range.
11. Review equity, acceptability and implementation consequences before treating the optimum as a recommendation.

Linear programming makes trade-offs explicit and reproducible when resources are limited. Its decision value comes from a credible formulation, transparent constraints and careful interpretation of both the optimal allocation and the alternatives the model rules out.