Constrained Optimisation

Constrained Optimisation with Objectives, Constraints and Shadow Prices in Health Care Allocation

Constrained optimisation is the formal version of the question every health budget holder faces, namely, given limits that cannot be exceeded, which combination of services produces the most health. It matters in health economics because under strict assumptions the usual cost-effectiveness decision rule follows from a budget-constrained maximisation, and the cost-effectiveness threshold can be read as a by-product of that problem. An illustrative example below splits GBP 1 million between two programmes. Some problem classes have their own pages, namely linear programming, nonlinear programming, integer programming and multi-objective optimisation.

Decision variables, objective and constraints

The first ISPOR task force report on optimisation methods describes constrained optimisation as a set of methods for finding the best solution to a problem that has many potential solutions in the presence of identified constraints. Its components are the objective function, which the decision maker wants to maximise or minimise; the decision variables, the parts of the system being decided; and the constraints, restrictions on those variables, often about resources, that determine which values are allowed. Parameters, such as the cost of a treatment, are fixed inputs.

For a maximisation the general form is

$$\max_{x} \; f(x) \quad \text{subject to} \quad g_j(x) \le b_j, \quad j = 1, \dots, m$$

where $x = (x_1, \dots, x_n)$ is the vector of decision variables, $f(x)$ is the objective function, $g_j(x)$ is the amount of resource $j$ used by the decision $x$ and $b_j$ is the amount of resource $j$ available. Equality constraints and bounds such as $x_i \ge 0$ may be added. The decisions that satisfy every constraint form the feasible set; if none does, the problem is infeasible, and the report advises changing it, for example by relaxing a constraint, before looking for an optimum.

The report's illustration is a health centre with one hour of consulting time, 15 minutes per patient and a USD 150 medicines budget. Regular patients gain two units of health for USD 25 of medicines and severe patients three units for USD 50; the optimum, two of each, gives 10 units and uses the whole hour and the whole budget.

Why health resource allocation is a budget-constrained maximisation

The same report lists allocation within and across disease programmes as a typical application, in which a health authority or insurance fund chooses which interventions to fund to maximise population health, subject to the overall health budget and legal constraints on equity. The second task force report adds that the task central to health economic analysis, comparing an ICER with a critical threshold, is related to budget-constrained optimisation. Citing Weinstein and Zeckhauser, it states that under a strict set of assumptions the threshold is the inverse of the shadow price of the budget constraint.

Stinnett and Paltiel argued that earlier treatments of allocation under a budget relied on unnecessarily restrictive assumptions, and showed that a general programming framework can handle returns to scale, partial and complete indivisibility and interdependence between programmes, as well as ethical constraints with an explicit cost of equity. Epstein and colleagues observed that the standard decision rules require either a threshold or a fixed budget, that in practice neither is generally taken, and that mathematical programming generalises those rules.

The Lagrangian and the Karush-Kuhn-Tucker conditions

Boyd and Vandenberghe describe Lagrangian duality as taking the constraints into account by adding a weighted sum of the constraint functions to the objective. The weights are the Lagrange multipliers. For the maximisation above the Lagrangian is

$$\mathcal{L}(x, \lambda) = f(x) - \sum_{j=1}^{m} \lambda_j \left( g_j(x) - b_j \right)$$

where $\lambda_j \ge 0$ is the multiplier attached to constraint $j$ and the other terms are as defined above. When the functions are differentiable, an optimal decision $x^*$ with multipliers $\lambda^*$ satisfies the Karush-Kuhn-Tucker conditions, here in maximisation form.

$$\nabla f(x^*) = \sum_{j=1}^{m} \lambda_j^* \nabla g_j(x^*), \qquad g_j(x^*) \le b_j, \qquad \lambda_j^* \ge 0, \qquad \lambda_j^* \left( g_j(x^*) - b_j \right) = 0$$

where $\nabla$ denotes the vector of partial derivatives with respect to the decision variables. The parts are stationarity, primal feasibility, dual feasibility and complementary slackness. Boyd and Vandenberghe state them as necessary conditions when strong duality holds, and show that for a convex problem any point satisfying them is optimal.

Two of the conditions have a direct economic reading. With a single budget constraint, stationarity says that every funded programme yields the same marginal health gain per pound, equal to $\lambda$, which is the equal-margins rule behind marginal analysis and allocative efficiency. Complementary slackness says that a constraint with spare capacity has a zero multiplier, so loosening it gains nothing. Maximising a concave objective under convex constraints is a convex problem, in which any local optimum is also global. Without convexity, local methods give no guarantee of finding the best solution, and the ISPOR report recommends repeating the search from different starting values.

Shadow prices and the value of one more unit of a constraint

Boyd and Vandenberghe show that, when the optimal value is differentiable and strong duality holds, the optimal multipliers are exactly the local sensitivities of the optimal value to small changes in the constraints. This is what turns a multiplier into a price. Writing $V(b)$ for the best achievable objective at resource levels $b$ gives the following.

$$\lambda_j^* = \frac{\partial V(b)}{\partial b_j}, \qquad V(b) = \max_{x} \left\{ f(x) : g_j(x) \le b_j \text{ for all } j \right\}$$

where $V(b)$ is the optimal value function and $\lambda_j^*$ is the shadow price of resource $j$. They read the multiplier as roughly the extra gain from a small increase in a resource, and so its natural price. The second ISPOR report applies the idea to health, defining the shadow price as how much QALYs would increase for a one-unit increase in the budget. The budget constraint page takes this reading further.

Worked example splitting GBP 1 million between two programmes

The programmes, functions and numbers below are illustrative. A commissioner divides GBP 1 million between cardiac rehabilitation (A) and falls prevention (B), both with diminishing returns.

1. Formulate the problem.

$$\max_{x, y} \; 4\sqrt{x} + 2\sqrt{y} \quad \text{subject to} \quad x + y \le 1000, \quad x \ge 0, \quad y \ge 0$$

where $x$ and $y$ are spending on programmes A and B in thousands of pounds and the objective is QALYs gained.

2. Apply stationarity. The marginal QALY gains per GBP 1,000 are $\partial Q / \partial x = 2/\sqrt{x}$ for A and $\partial Q / \partial y = 1/\sqrt{y}$ for B, and both must equal $\lambda$. So $\sqrt{x} = 2\sqrt{y}$, which means $x = 4y$. Both marginal gains are positive, so the budget binds and $x + y = 5y = 1000$, giving $y = 200$ and $x = 800$.

3. Value the allocation. Total health gain is $Q = 4\sqrt{800} + 2\sqrt{200} = 113.14 + 28.28 = 141.42$ QALYs. An equal split gives $Q = 4\sqrt{500} + 2\sqrt{500} = 89.44 + 44.72 = 134.16$ QALYs, so the optimum yields 7.26 more QALYs from the same money.

4. Read the shadow price. At the optimum $\lambda = 2/\sqrt{800} = 1/\sqrt{200} = 0.0707$ QALYs per GBP 1,000. Its inverse, about GBP 14,142 per QALY, is the cost per QALY of the last pound in either programme and the threshold this budget implies. The average cost per QALY, GBP 800,000 for 113.14 QALYs in A and GBP 200,000 for 28.28 QALYs in B, is about GBP 7,071 in both, so the threshold is a marginal quantity, here twice the average.

5. Test the shadow price on a larger change. Because the optimum always puts 80% of the budget into A, the value function is $V(B) = \sqrt{20B}$, with $B$ in thousands of pounds. Adding GBP 100,000 lifts it from $V = \sqrt{20000} = 141.42$ to $V = \sqrt{22000} = 148.32$, a gain of 6.90 QALYs. The shadow price predicts 0.0707 × 100 = 7.07 QALYs, an overstatement that grows with the size of the change.

6. Add a policy constraint. The commissioner now commits to spending at least GBP 300,000 on falls prevention, so $y \ge 300$. The earlier optimum spends only 200, so the constraint binds, giving $y = 300$ and $x = 700$. Health gain falls to $Q = 4\sqrt{700} + 2\sqrt{300} = 105.83 + 34.64 = 140.47$ QALYs, a loss of 141.42 − 140.47 = 0.95 QALYs. The budget multiplier becomes $\lambda = 2/\sqrt{700} = 0.0756$, and the multiplier on the floor is the gap between the two marginal gains, $\mu = 0.0756 - 1/\sqrt{300} = 0.0756 - 0.0577 = 0.0179$ QALYs lost for each extra GBP 1,000 of required spending on B. A floor of GBP 150,000 would have been slack, with a zero multiplier and an unchanged allocation.

7. Interpretation. The optimisation makes the price of the commitment visible, 0.95 QALYs at this budget, which the commissioner can weigh against the reason for the floor. The constraint also moves the implied threshold from about GBP 14,142 to about GBP 13,229 per QALY, because the marginal pound now goes to the programme held below its efficient share.

Problem classes and solution methods

The first ISPOR report classifies problems as linear or nonlinear, deterministic or stochastic, continuous or discrete, and single or multi-objective, and the solution method has to match the class. Exact methods include the simplex method for linear problems and Newton or interior point methods for nonlinear ones; heuristics such as genetic algorithms give approximate solutions where an exact approach is unavailable or too costly. The report warns that solving an integer problem as a linear one and rounding the answer can give an infeasible solution, or a feasible one that is not the integer optimum. Where parameters are uncertain, stochastic programming and robust optimisation build the uncertainty into the problem, and general iterative search is covered under numerical optimisation.

The second ISPOR report's first case study chose the mix of cervical cancer screening and vaccination strategies that minimised expected cancer cases under a fixed budget and coverage limits, as a linear programme with 52 decision variables and 57 constraints solved by the simplex method in Excel Solver. Costs and cases for each strategy came from a Markov model.

Constrained optimisation alongside economic evaluation

The first ISPOR report contrasts optimisation with the models used in health technology assessment. A Markov model estimates the costs and effects of different diagnostic and treatment options, and decisions based on it may not formally consider the constraints and resource implications in the system; capacity constraints are usually neglected. Optimisation brings the budget and other limits, such as staff and beds, into the problem itself. The second report adds that reimbursement processes take budget constraints only partly into account.

Epstein and colleagues argued that a rule which is neither a true threshold nor a fixed budget may be inconsistent with the budget and cannot identify the programme to be displaced at the margin. Their framework reports the health forgone under each budgetary policy and equity concern, like the 0.95 QALYs in the example. The ISPOR report adds that showing how much health an equity objective costs can be useful even if the optimum is not adopted.

What the optimum depends on, and common misreadings

An optimal solution is optimal only for the problem as written. The ISPOR report notes that a model used for optimisation must be valid for every combination of decision variables, and that a mathematically optimal answer, such as a nurse roster that breaks up existing teams, may not be implementable. The recurring errors are these.

1. Treating the objective as neutral. Maximising total QALYs ignores who gains; equity concerns enter as constraints or weights, with their cost reported, as in step 6.
2. Using a shadow price for a large change. The multiplier is a local sensitivity. In the example it overstated the gain from GBP 100,000 of extra budget, and McCabe and colleagues argue that interventions with a large budget impact may need a lower threshold because they displace more than the marginal activities.
3. Taking solver convergence as proof of a global optimum. That holds only for convex problems; others need restarts from different starting values.
4. Treating parameters as certain. The ISPOR report recommends re-running the optimisation with different parameter values to see how far the solution and optimal value move.

Sources

• Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press; 2004. Sections 1.4.1, 4.2.2, 5.1.1, 5.5.3 and 5.6.3. https://web.stanford.edu/~boyd/cvxbook/
• Crown W, Buyukkaramikli N, Thokala P, Morton A, Sir MY, Marshall DA, Tosh J, Padula WV, Ijzerman MJ, Wong PK, Pasupathy KS. Constrained optimization methods in health services research: an introduction. Report 1 of the ISPOR Optimization Methods Emerging Good Practices Task Force. Value in Health. 2017;20(3):310-319. https://doi.org/10.1016/j.jval.2017.01.013
• Crown W, Buyukkaramikli N, Sir MY, Thokala P, Morton A, Marshall DA, Tosh JC, Ijzerman MJ, Padula WV, Pasupathy KS. Application of constrained optimization methods in health services research: report 2 of the ISPOR Optimization Methods Emerging Good Practices Task Force. Value in Health. 2018;21(9):1019-1028. https://doi.org/10.1016/j.jval.2018.05.003
• Epstein DM, Chalabi Z, Claxton K, Sculpher M. Efficiency, equity, and budgetary policies: informing decisions using mathematical programming. Medical Decision Making. 2007;27(2):128-137. https://doi.org/10.1177/0272989X06297396
• McCabe C, Claxton K, Culyer AJ. The NICE cost-effectiveness threshold: what it is and what that means. PharmacoEconomics. 2008;26(9):733-744. https://doi.org/10.2165/00019053-200826090-00004
• Stinnett AA, Paltiel AD. Mathematical programming for the efficient allocation of health care resources. Journal of Health Economics. 1996;15(5):641-653. https://doi.org/10.1016/S0167-6296(96)00493-6