Integer Programming

Integer Programming for Funding Indivisible Programmes and Medicines Within a Budget

Integer programming gives a health system payer a formal way to pick the package of programmes, medicines or services that delivers the most health, usually counted in QALYs, without spending more than a fixed budget. Each candidate becomes a yes-or-no decision variable, and that matters because most funding decisions cannot be taken in fractions. When options are indivisible, ranking them by cost per QALY and funding down the list until the money runs out can miss the best affordable package. Earnshaw and Dennett suggested that formulary, drug development and pricing decisions could benefit from mathematical programming.

The fixed-budget funding decision as a knapsack problem

The second report of the ISPOR good practices task force on optimisation methods treats the fixed-budget funding decision as an obvious example of constrained optimisation, describing a planner with a number of investment opportunities and a fixed budget that cannot fund them all. It frames choosing the best set to fund, for example to maximise total QALYs, as an optimisation problem, citing the operations research literature on knapsack problems. In health care the knapsack is the budget and the items are programmes or medicines.

The first task force report names the building blocks of any such model as an objective function to maximise or minimise, decision variables that represent the choices, constraints that restrict those choices (often resources), and parameters such as the cost of each treatment. For a payer choosing which of $n$ new options to add to current care, the simplest binary version is as follows.

$$\max \sum_{i=1}^{n} q_i x_i \quad \text{subject to} \quad \sum_{i=1}^{n} c_i x_i \le B, \qquad x_i \in \{0, 1\}$$

where $q_i$ is the QALY gain from funding option $i$ instead of current care, $c_i$ is the cost that option would draw from the budget over the budget period, $B$ is the budget available and $x_i$ equals 1 if option $i$ is funded and 0 if it is not. The objective and the constraint are linear, so the only difference from linear programming is that each $x_i$ must be a whole number. The costs are what a budget impact analysis estimates for each option; the QALY gains come from the appraisal models. Integer variables can also count indivisible units, such as clinics, scanners or staff posts, rather than take only the values 0 and 1.

Why indivisibility breaks the cost-per-QALY ranking rule

The familiar shortcut is to rank options by their incremental cost-effectiveness ratio, as in a cost-effectiveness league table, and fund from the top until the budget is exhausted. Sendi and Al point out that this classical decision rule assumes health care programmes are completely divisible, and argue that they cannot be, since individuals are not divisible; they therefore propose an integer programming approach to budget allocation in place of a linear one. Stinnett and Paltiel had earlier argued that previous treatments of budget-constrained allocation rested on unnecessarily restrictive assumptions, and showed that a general mathematical programming framework can handle partial and complete indivisibility, returns to scale and dependence between programmes.

The link with the cost-effectiveness threshold runs through the shadow price of the budget. The second ISPOR report notes that, under a strict set of assumptions, the threshold is the inverse of the shadow price of the budget constraint, the shadow price being how much the objective in QALYs would rise for one more unit of budget. When options are independent and can be scaled smoothly at a constant cost per QALY, funding in ICER order until the budget runs out reproduces the optimum, and the ICER of the last option funded is the threshold. With all-or-nothing options it need not, and the shadow price, and so the threshold link, is only approximate, because the last affordable option can leave money unspent while a different combination would have used the whole budget for more health.

Epstein and colleagues describe the practical gap. The standard rules of cost-effectiveness analysis require either a threshold or a fixed overall budget, neither is generally set in practice, and the rule actually followed may be inconsistent with the budget and cannot identify which programme should be displaced at the margin. They describe mathematical programming as a generalisation of the standard decision rules.

Worked example with four indivisible programmes and a 10 million pound budget

The programmes, costs and QALY gains below are illustrative. A regional payer has £10 million for new programmes over the budget period, and each programme must be funded in full or not at all.

1. Ratios. Programme A costs 6,000,000 / 240 = £25,000 per QALY, B costs 5,000,000 / 190 = 26,316, C costs 5,000,000 / 185 = 27,027 and D costs 2,000,000 / 50 = 40,000.

2. The ranking rule. Funding in ratio order buys A first, leaving 10 − 6 = 4 million. B and C each cost 5 million and no longer fit, so they are skipped; D fits, leaving 4 − 2 = 2 million unspent. The package A plus D costs 8 million and gains 240 + 50 = 290 QALYs.

3. The integer optimum. Four binary variables give 2 × 2 × 2 × 2 = 16 possible packages. Eight of them fit the budget besides funding nothing, namely A, B, C and D alone, A plus D (8 million, 290 QALYs), B plus C (10 million, 375 QALYs), B plus D (7 million, 240 QALYs) and C plus D (7 million, 235 QALYs). Every package with three or four programmes costs at least 12 million. The optimum is B plus C, which uses the whole budget and gains 190 + 185 = 375 QALYs.

4. The divisible benchmark. If programmes could be funded in fractions, the linear programming answer would be all of A plus 4/5 of B, giving 240 + 0.8 × 190 = 392 QALYs. Rounding that fraction down leaves A alone, and rounding it up breaks the budget, which is the trap the first ISPOR report warns about, since a rounded linear solution may be infeasible, or feasible but not optimal.

5. Interpretation. The optimum gains 375 − 290 = 85 more QALYs than the ranking rule, about 29% more, for the same budget, and it does so by skipping the programme with the best ratio. The gap between 392 and 375 QALYs is the health lost purely to indivisibility.

Mixed-integer extensions for set-up costs, capacity and equity

Mixed-integer programming combines binary choices with continuous ones. A screening or vaccination programme may need a fixed set-up cost before anyone can be covered, after which coverage can be scaled, as below.

$$\text{cost}_i = F_i y_i + v_i z_i, \qquad z_i \le N_i y_i, \qquad y_i \in \{0, 1\}, \quad z_i \ge 0$$

where $F_i$ is the set-up cost of programme $i$, $y_i$ is 1 if it is set up, $v_i$ is the cost per person covered, $z_i$ is the number covered and $N_i$ the eligible population. Coverage can be positive only if the set-up cost is paid, which is the partial indivisibility and returns to scale that Stinnett and Paltiel showed a programming framework can absorb.

Further constraints add other limits. The first ISPOR report notes that capacity constraints are usually neglected in health economic models although planners cannot ignore them; limits on staff, beds or consultation time enter as extra inequalities in the same variables.

Equity concerns can be written as constraints too. Epstein and colleagues argue that indivisibility within a patient population is in effect a concern for horizontal equity, represent this and other equity concerns as constraints, and estimate the opportunity cost of each, and Stinnett and Paltiel showed how ethical constraints yield an explicit cost of equity. In the illustrative example, a rule that programme D must be funded because it serves the group with the worst health gives a best package of A plus D at 290 QALYs (the same package the ranking rule picked), so the equity rule costs 375 − 290 = 85 QALYs. A linear programming model of four interventions for newly diagnosed type 2 diabetes by Earnshaw and colleagues likewise maximised QALYs under budget and equity constraints and found the effect of the equity constraints extensive.

Realistic problems are solved by algorithms, not enumeration. The second ISPOR report names branch-and-bound as an exact method for mixed-integer models and notes that large models may need heuristics that give a good but not necessarily optimal solution in reasonable time; its cervical cancer case was solved in Microsoft Excel with the Solver add-in.

Using the results in health technology assessment

The model returns a package, the health it buys and, by re-solving with constraints removed or tightened, the health forgone to each constraint. The second ISPOR report concludes that such methods show decision makers the optimal target and the size of the loss of benefit, or rise in cost, associated with the choice finally made. That makes the opportunity cost of a budget rule, an equity rule or a capacity limit visible in QALYs.

The first ISPOR report observes that the focus of health economics is usually relative efficiency without explicit consideration of the budget, because many jurisdictions do not implement a constrained budget explicitly. Earnshaw and Dennett list simultaneous handling of several constraints and built-in sensitivity analysis among the attractions of mathematical programming models, while noting that their use in economic evaluations of new technologies had been limited. Re-running the model across a range of budgets, as the cervical cancer case did when it varied the budget from 20% below to 150% above the pre-vaccination level, shows which options enter or leave the package as funding changes and supports marginal analysis of what to add or remove.

Limitations and common misreadings

The optimum is only as good as the candidate list and the inputs. The model needs costs and QALY gains for every option on a common basis, and when Mason, Drummond and Torrance examined the source studies behind a published league table they found differences in year of origin, discount rates, health state valuations, settings and comparators; the same incompatibilities carry into an integer programming model. The simple binary form also assumes that each option's costs and benefits add up independently, yet the second ISPOR report gives infectious disease as a case where investing in vaccination may leave fewer cases to treat, so options interact, and the interaction has to be written into the model with extra variables or constraints.

A deterministic model treats every cost and QALY as fixed; the first ISPOR report contrasts this with stochastic optimisation, where uncertainty is built in. Sendi and Al extend the integer approach to maximise expected effects while limiting the probability of exceeding the budget to a chosen level such as 0.05, Al and colleagues replace the fixed budget with a flexible one governed by a value function over money and health, and McKenna and colleagues develop a two-stage stochastic formulation in which the value of further research depends on the budgetary policy and the remedial actions available. Stochastic programming and robust optimisation have their own pages.

Three misreadings follow from the example. As the example shows, a package that skips the option with the best ratio is not automatically wrong. Rounding a linear programming answer is not the same as solving the integer problem. An optimal package is optimal only for the stated objective and constraints, so concerns left out of the model, such as severity or need not captured by QALYs, still require deliberation.

Sources

• Al MJ, Feenstra TL, van Hout BA. Optimal allocation of resources over health care programmes: dealing with decreasing marginal utility and uncertainty. Health Economics. 2005;14(7):655-667. https://doi.org/10.1002/hec.973
• 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
• Earnshaw SR, Dennett SL. Integer/linear mathematical programming models: a tool for allocating healthcare resources. PharmacoEconomics. 2003;21(12):839-851. https://doi.org/10.2165/00019053-200321120-00001
• Earnshaw SR, Richter A, Sorensen SW, Hoerger TJ, Hicks KA, Engelgau M, Thompson T, Narayan KMV, Williamson DF, Gregg E, Zhang P. Optimal allocation of resources across four interventions for type 2 diabetes. Medical Decision Making. 2002;22(5 Suppl):S80-S91. https://doi.org/10.1177/027298902237704
• 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
• Mason J, Drummond M, Torrance G. Some guidelines on the use of cost effectiveness league tables. BMJ. 1993;306(6877):570-572. https://doi.org/10.1136/bmj.306.6877.570
• McKenna C, Chalabi Z, Epstein D, Claxton K. Budgetary policies and available actions: a generalisation of decision rules for allocation and research decisions. Journal of Health Economics. 2010;29(1):170-181. https://doi.org/10.1016/j.jhealeco.2009.11.005
• Sendi P, Al MJ. Revisiting the decision rule of cost-effectiveness analysis under certainty and uncertainty. Social Science & Medicine. 2003;57(6):969-974. https://doi.org/10.1016/S0277-9536(02)00477-X
• 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