Integer optimum of the 0-1 funding problem for four indivisible programmes with its gaps to a funding rule and to the divisible fill

Each of the 15 packages that fund at least one of four programmes contributes its total QALYs when its total cost is at most the budget and zero when it is not, and H_star is the largest contribution, the optimum of the article's binary problem of maximising the sum of q_i x_i subject to the sum of c_i x_i at most B with each x_i equal to 0 or 1. Funding nothing gives zero, so H_star is zero when no programme fits. G_rule is the health that a funding rule's package, with health H_rule, leaves unbought at the same budget, the loss of benefit that Crown and colleagues say optimisation shows for the choice finally made, and with H_rule taken from HE-FM-CELT-003 it is the gain of the optimum over the league table. L_ind is the health the divisible fill of HE-FM-CELT-001, H_div, buys above the optimum, the health lost purely because programmes cannot be split (derived). The formula is written out for four programmes so that it runs as calculator text, and HE-CF-IPH-001 does the same search for any number.

Signature

H_star = max(max(max(max(max(max(max(max(max(max(max(max(max(max((c_1 <= B) * q_1, (c_2 <= B) * q_2), (c_3 <= B) * q_3), (c_4 <= B) * q_4), (c_1 + c_2 <= B) * (q_1 + q_2)), (c_1 + c_3 <= B) * (q_1 + q_3)), (c_1 + c_4 <= B) * (q_1 + q_4)), (c_2 + c_3 <= B) * (q_2 + q_3)), (c_2 + c_4 <= B) * (q_2 + q_4)), (c_3 + c_4 <= B) * (q_3 + q_4)), (c_1 + c_2 + c_3 <= B) * (q_1 + q_2 + q_3)), (c_1 + c_2 + c_4 <= B) * (q_1 + q_2 + q_4)), (c_1 + c_3 + c_4 <= B) * (q_1 + q_3 + q_4)), (c_2 + c_3 + c_4 <= B) * (q_2 + q_3 + q_4)), (c_1 + c_2 + c_3 + c_4 <= B) * (q_1 + q_2 + q_3 + q_4)); G_rule = H_star - H_rule; L_ind = H_div - H_star
Inputs
InputsDefinitionUnit
c_1Cost that programme 1 would draw from the budget over the budget period if funded in full, above zerocurrency
BBudget available for new programmes over the budget period, in the same currency unit as the costscurrency
q_1QALY gain from funding programme 1 in full instead of current care, above zeroQALYs
c_2Cost that programme 2 would draw from the budget over the budget period if funded in full, above zerocurrency
q_2QALY gain from funding programme 2 in full instead of current care, above zeroQALYs
c_3Cost that programme 3 would draw from the budget over the budget period if funded in full, above zerocurrency
q_3QALY gain from funding programme 3 in full instead of current care, above zeroQALYs
c_4Cost that programme 4 would draw from the budget over the budget period if funded in full, above zerocurrency
q_4QALY gain from funding programme 4 in full instead of current care, above zeroQALYs
H_ruleTotal QALY gain of the package that a funding rule chooses at the same budget and inputs, such as H_w of HE-FM-CELT-003 for the league table of whole programmesQALYs
H_divTotal QALY gain of the divisible fill of HE-FM-CELT-001 at the same budget and inputs, with the marginal programme part-fundedQALYs
Output
H_starInteger optimum, the largest total QALY gain of any package of whole programmes whose total cost is at most the budget, zero when none fitsQALYs
G_ruleQALYs by which the integer optimum exceeds the funding rule's package, zero when the rule finds an optimal packageQALYs
L_indQALYs by which the divisible fill exceeds the integer optimum, the health lost to indivisibilityQALYs

Function

0-1 integer programming function for funding indivisible health programmes within a fixed budget

Takes the QALY gain q_i and the budget cost c_i of each of n candidate programmes or medicines, each funded in full or not at all, and a fixed budget B, and returns the package of funding decisions x_i, each 0 or 1, that gives the most QALYs with the cost of the package at most B, together with the QALYs H_star it buys. The league-table rule for whole programmes, HE-FM-CELT-003, funds in ascending order of ICER and passes over a programme that no longer fits, so it returns a package that fits the budget but not always the best one, and the divisible fill of HE-FM-CELT-001, filled for a whole table by HE-CF-CELT-001, part-funds the marginal programme and so gives health that whole programmes may not be able to deliver. Neither record searches the packages, and HE-FM-CELT-003 leaves the best choice of whole programmes to this article. HE-FM-IPH-001 gives H_star for four programmes by checking every package, with its gap to the health of a funding rule and its distance below the divisible fill, and HE-CF-IPH-001 enumerates the packages for any number of programmes and adds programmes that a rule requires to be funded. The critical ratio of a league table is HE-FM-CELT-002 and the budget implied by a threshold is HE-FM-CELT-004; shadow prices and Lagrangian conditions belong to the Constrained Optimisation article. The article's set-up cost form, a fixed cost switched on by a binary set-up variable plus a cost per person covered, is a model-building device for mixed-integer programmes and is not drafted here. Notation follows the Integer Programming article.

Computational function

  • Computational function for the best package of whole programmes by enumerating every package within the budget

    Takes the names, budget costs and QALY gains of any number of independent programmes, a budget and the names of any programmes a rule requires to be funded, checks every one of the 2^n packages of whole programmes, and returns the best package that fits the budget and includes the required programmes, with its cost, its QALYs and the number of packages that qualify. Run once without and once with the required programmes, it gives the health forgone to the rule, the explicit cost of equity that Stinnett and Paltiel describe and the opportunity cost of an equity constraint that Epstein and colleagues estimate. The inputs are lists of programmes, not the scalar inputs of HE-FM-IPH-001. The Math / Code line shows four programmes with programme 4 required, and the R and Python versions take any number of programmes and any required set.

    Inputs and outputs: name is the label of each programme; cost is its budget cost over the budget period, above zero; qaly is its QALY gain against current care, above zero; B is the budget in the units of cost; must names the programmes that must be funded, empty by default, as a character vector in R and as a tuple or list in Python, such as ("D",). In the Math / Code line c_1 to c_4 and q_1 to q_4 are the four programmes' costs and QALY gains, H_star is the integer optimum of HE-FM-IPH-001, H_must is the best total with programme 4 funded, and E_must is the QALYs forgone to the requirement. The R and Python versions return the names in the best package, its cost, its QALYs and the number of qualifying packages, the empty package included when nothing is required.

    Assumption: Programmes are whole, independent and additive on one basis (HE-AS-IPH-001, HE-AS-IPH-002), and the required programmes together cost no more than B; when they cost more, no package qualifies and the R and Python versions return NULL or None. Among packages with equal QALYs the first in enumeration order is returned, the package whose binary number, with programme 1 as the lowest digit, is smallest (HE-AS-IPH-003). The H_must line assumes c_4 is at most B.

    Worked example (Article's equity rule with D required): With GBP 10 million and D required because it serves the group with the worst health, the best package is A plus D for 290 QALYs, so the rule costs 85 QALYs, as in the article, and four packages qualify. Money is in GBP millions. c_1 = 6; c_2 = 5; c_3 = 5; c_4 = 2; q_1 = 240; q_2 = 190; q_3 = 185; q_4 = 50; B = 10; H_star = 375; H_must = 290; E_must = 85

    Worked example (D required at GBP 12 million): With an illustrative GBP 12 million the best package is A plus B for 430 QALYs, and with D required it is B plus C plus D for 425, so the rule costs 5 QALYs (computed here for illustration). Money is in GBP millions. c_1 = 6; c_2 = 5; c_3 = 5; c_4 = 2; q_1 = 240; q_2 = 190; q_3 = 185; q_4 = 50; B = 12; H_star = 430; H_must = 425; E_must = 5

    Worked example (Article's optimum from the R and Python code): ip_best(c("A", "B", "C", "D"), c(6, 5, 5, 2), c(240, 190, 185, 50), 10) returns the package B and C, cost 10, 375 QALYs and 9 qualifying packages, and with must = "D" it returns A and D, cost 8, 290 QALYs and 4 qualifying packages. This example is for reading against the R and Python code; its calculator form is HE-EX-IPH-001.

    Excel: On the sheet of HE-IM-IPH-001, with a column range named MustFund (D2 to D5) holding 1 for each required programme and 0 otherwise, enter =MMULT(E2:H2,MustFund) in L2 for the number of required programmes in the package and =(I2<=Budget)*(L2=SUM(MustFund))*J2 in M2, and fill both down to row 17. Then =MAX(M2:M17) in a cell named ForcedOptimum gives the best total with the requirement, =MATCH(ForcedOptimum,M2:M17,0) in BestPackageRow gives the row of PackageMatrix that holds the package, the first such row when packages tie, and =IntegerOptimum-ForcedOptimum in EquityRuleCost gives the QALYs forgone. MustFund needs a 0 typed for each programme not required, since MMULT returns #VALUE! when a cell is blank. When the required programmes cost more than Budget no package qualifies, and the sheet then gives a ForcedOptimum of 0, a BestPackageRow of 1 (the empty package) and an EquityRuleCost equal to IntegerOptimum, so a ForcedOptimum of 0 with a programme required reads as no qualifying package. For more than four programmes PackageMatrix needs 2^n rows and n columns.

    R: ip_best <- function(name, cost, qaly, B, must = character(0)) { n <- length(cost); best <- NULL; hb <- -Inf; feas <- 0; for (k in 0:(2^n-1)) { x <- as.numeric(bitwAnd(k, 2^(0:(n-1))) > 0); if (sum(x*cost) <= B && all(x[name %in% must] == 1)) { feas <- feas+1; h <- sum(x*qaly); if (h > hb) { hb <- h; best <- x } } }; if (is.null(best)) return(NULL); list(package = name[best == 1], cost = sum(best*cost), qalys = hb, qualifying = feas) } The strict comparison keeps the first optimal package, and bitwAnd limits n to 31.

    Python: def ip_best(name, cost, qaly, B, must=()): pk = [[(k >> j) & 1 for j in range(len(cost))] for k in range(2**len(cost))]; ok = [x for x in pk if sum(a*c for a, c in zip(x, cost)) <= B and all(x[name.index(m)] for m in must)]; best = max(ok, key=lambda x: sum(a*q for a, q in zip(x, qaly)), default=None); return None if best is None else ([nm for nm, a in zip(name, best) if a], sum(a*c for a, c in zip(best, cost)), sum(a*q for a, q in zip(best, qaly)), len(ok)) Plain Python with no imports; max returns the first optimal package in enumeration order.

    Test (Article's equity rule): With MustFund holding 0, 0, 0 and 1 for the article's inputs, ForcedOptimum is 290 and EquityRuleCost 85. Expected result TRUE. FALSE shows an M column without the requirement test, which returns 375 and a cost of 0, and a doubled ForcedOptimum of 580 or a halved one of 145. Excel check =AND(ABS(ForcedOptimum-290)<0.000001,ABS(EquityRuleCost-85)<0.000001)

    Test (Nothing required): With MustFund all 0 the requirement test passes for every package, so ForcedOptimum equals IntegerOptimum, 375 for the article's inputs, a limiting case. Expected result TRUE. FALSE shows an M column that tests L2 against 1 in place of SUM(MustFund), which leaves out the packages with no required programme and returns 0, and a doubled or halved ForcedOptimum. Excel check =ABS(ForcedOptimum-IntegerOptimum)<0.000001

    Common error (Enumerating a large candidate list): The number of packages doubles with each programme, 16 for 4, 1,048,576 for 20 and 1,073,741,824 for 30, so complete enumeration suits short candidate lists only. Crown and colleagues name branch-and-bound as an exact solution algorithm for mixed-integer models and describe heuristics that give a good but not necessarily optimal solution in reasonable time.

    Source: 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. Abstract, on representing indivisibility in a patient population as a concern for horizontal equity, representing equity concerns as constraints in the programme and estimating the opportunity costs of a range of equity concerns. Stinnett AA, Paltiel AD. Mathematical programming for the efficient allocation of health care resources. Journal of Health Economics. 1996;15(5):641-653. Abstract, on ethical constraints and the explicit identification of the cost of equity. Crown W et al. 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. Appendix 1, Educational Case Study (accepted manuscript), on using a heuristic in place of an exact solution algorithm such as branch-and-bound for a mixed-integer programming model.

    H_star = max(max(max(max(max(max(max(max(max(max(max(max(max(max((c_1 <= B) * q_1, (c_2 <= B) * q_2), (c_3 <= B) * q_3), (c_4 <= B) * q_4), (c_1 + c_2 <= B) * (q_1 + q_2)), (c_1 + c_3 <= B) * (q_1 + q_3)), (c_1 + c_4 <= B) * (q_1 + q_4)), (c_2 + c_3 <= B) * (q_2 + q_3)), (c_2 + c_4 <= B) * (q_2 + q_4)), (c_3 + c_4 <= B) * (q_3 + q_4)), (c_1 + c_2 + c_3 <= B) * (q_1 + q_2 + q_3)), (c_1 + c_2 + c_4 <= B) * (q_1 + q_2 + q_4)), (c_1 + c_3 + c_4 <= B) * (q_1 + q_3 + q_4)), (c_2 + c_3 + c_4 <= B) * (q_2 + q_3 + q_4)), (c_1 + c_2 + c_3 + c_4 <= B) * (q_1 + q_2 + q_3 + q_4)); H_must = q_4 + max(max(max(max(max(max((c_4 + c_1 <= B) * q_1, (c_4 + c_2 <= B) * q_2), (c_4 + c_3 <= B) * q_3), (c_4 + c_1 + c_2 <= B) * (q_1 + q_2)), (c_4 + c_1 + c_3 <= B) * (q_1 + q_3)), (c_4 + c_2 + c_3 <= B) * (q_2 + q_3)), (c_4 + c_1 + c_2 + c_3 <= B) * (q_1 + q_2 + q_3)); E_must = H_star - H_must

Try this function

Implementations

  • Excel

    Integer optimum of four whole programmes from a package matrix in named cells

    With the four programmes' costs in a column range named ProgCosts (B2 to B5), their QALY gains in ProgQALYs (C2 to C5) and the budget in Budget, the first formula, entered in E2 and filled to H17, builds a range named PackageMatrix whose row k holds the binary digits of k less 1, one column per programme, so its 16 rows are every package. In each row I2 holds the package cost, J2 its QALYs and K2 its QALYs when it fits and zero when it does not, each filled down to row 17, and the cell named IntegerOptimum takes the largest value in K2 to K17. With the health of the league table of whole programmes (WholeHealth of HE-IM-CELT-003, extended to four rows) in RuleHealth and the divisible fill of HE-CF-CELT-001 in DivisibleHealth, the last two formulas return the cells named GainOverRule and IndivisibilityLoss. MMULT of a one-row package and a four-row column of costs or QALYs is a single value, so it needs no array entry in an ordinary cell. MMULT returns #VALUE! when any cell of ProgCosts or ProgQALYs is blank or holds text, so every programme needs a number in both ranges.

    =MOD(INT((ROW()-ROW($E$2))/2^(COLUMN()-COLUMN($E$2))),2); =MMULT(E2:H2,ProgCosts); =MMULT(E2:H2,ProgQALYs); =(I2<=Budget)*J2; =MAX(K2:K17); =IntegerOptimum-RuleHealth; =DivisibleHealth-IntegerOptimum

Assumptions

  • Whole programmes, one budget and independent additive gains in the 0-1 funding problem

    Each programme is funded in full or not at all, the budget is the only constraint, and each programme's cost and QALY gain are the same whatever else is funded, so the cost and QALYs of a package are the sums over its programmes, as in the article's binary form. Crown and colleagues give infectious disease as a case where investments interact, since vaccination may leave fewer cases to treat, and such interactions need extra variables or constraints (HE-ER-IPH-003). Costs and QALY gains are fixed numbers, the deterministic case that Crown and colleagues contrast with stochastic optimisation.

  • Positive costs and QALY gains on one basis in the 0-1 funding problem

    Every c_i and q_i is above zero and all are measured against current care on one perspective, price year, discount rate and budget period, with c_i the draw on the budget in that period. A programme that costs no more than current care, gives no less health and is strictly better on at least one of the two dominates it under HE-FM-DOM-001 and is funded before the search with any saving added to B, as HE-AS-CELT-002 does for the league table.

  • Ties and comparison inputs for the integer optimum

    H_star is a single number, but Crown and colleagues note that two or more decisions may yield the same optimum, so the package behind it need not be unique, and HE-CF-IPH-001 reports the first optimal package in its enumeration order, a convention of this package. H_rule must be the health of a package that fits the same budget, so G_rule is zero or above, and H_div must be the divisible fill at the same inputs, which is never below H_star, so L_ind is zero or above (derived, with no exception in a check of 200,000 random four-programme cases).

Worked examples

  • Article's four programmes and GBP 10 million budget with the optimum B plus C

    The article's illustrative programmes A, B, C and D cost GBP 6, 5, 5 and 2 million and gain 240, 190, 185 and 50 QALYs, with GBP 10 million to spend, and money is in GBP millions. Eight packages fit besides funding nothing, and B plus C, which uses the whole budget, gives the most, 375 QALYs. The pass-over league table of HE-FM-CELT-003, with a fourth row added, funds A and then D for 290 QALYs, so G_rule is 85, about 29% more health for the same budget, and the divisible fill of HE-FM-CELT-001 funds A and 0.8 of B for 392 QALYs, so L_ind is 17, as in steps 3 to 5 of the article.

    c_1 = 6; c_2 = 5; c_3 = 5; c_4 = 2; q_1 = 240; q_2 = 190; q_3 = 185; q_4 = 50; B = 10; H_rule = 290; H_div = 392; H_star = 375; G_rule = 85; L_ind = 17

  • Integer optimum when the league table of whole programmes is already optimal at GBP 12 million

    With an illustrative budget of GBP 12 million for the same programmes, the best package is A plus B, GBP 11 million for 430 QALYs, ahead of B plus C plus D at 425. The same four-row league table funds A and B and then finds that neither C nor D fits, so it reaches the same 430 and G_rule is zero, while the divisible fill adds 0.2 of C for 467 QALYs, so 37 QALYs are still lost to indivisibility (computed here for illustration). Money is in GBP millions.

    c_1 = 6; c_2 = 5; c_3 = 5; c_4 = 2; q_1 = 240; q_2 = 190; q_3 = 185; q_4 = 50; B = 12; H_rule = 430; H_div = 467; H_star = 430; G_rule = 0; L_ind = 37

  • Integer optimum when the budget covers every programme

    With an illustrative GBP 18 million every programme fits, the package of all four costs GBP 18 million and buys 665 QALYs, and the league table and the divisible fill reach the same total, so both gaps are zero, a limiting case in which the budget does not bind. Money is in GBP millions.

    c_1 = 6; c_2 = 5; c_3 = 5; c_4 = 2; q_1 = 240; q_2 = 190; q_3 = 185; q_4 = 50; B = 18; H_rule = 665; H_div = 665; H_star = 665; G_rule = 0; L_ind = 0

Common errors

  • Rounding the divisible answer in place of solving the 0-1 funding problem

    For the article's programmes the divisible answer funds A and 0.8 of B. Rounding the share of B up gives A plus B at GBP 11 million, over the GBP 10 million budget, and rounding it down gives A alone at 240 QALYs, 135 below the optimum of 375 (computed here for illustration). Crown and colleagues warn that a rounded solution may be infeasible, or feasible but not optimal.

  • Reporting the divisible fill as the health a budget buys from whole programmes

    The divisible fill of the article's table reports 392 QALYs for GBP 10 million, but no package of whole programmes buys more than 375, so 17 of the reported QALYs cannot be delivered. H_div is a ceiling on H_star for independent programmes, not an achievable total, as HE-ER-CELT-006 shows for the league table.

  • Adding the gains of programmes that serve overlapping patients

    If B and C in the article's table served overlapping patients, so that funding both gained an illustrative 280 QALYs in place of 375, the additive model would still choose B plus C and report 375, while A plus D, at 290, would then be the better package by 10 QALYs (computed here for illustration). Interacting programmes need a joint cost and gain for the combination, or extra variables and constraints, before the search.

Sources

  • Crown and colleagues on the integer programme for a budget and its rounded linear solution

    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. Section A Simple Illustration of a Constrained Optimization Problem, which writes the problem of a health care centre as maximising health benefit f_R x_R + f_L x_L subject to a budget constraint c_R x_R + c_L x_L at most B and a time constraint, with the decision variables zero or above and integer, places it in linear optimisation because the objective and constraints are linear while the decision variables must be integers, and warns that rounding a linear solution can give an infeasible solution or, if feasible, one that is not optimal. Section Definition of Constrained Optimization notes that in some problems two or more different decisions may yield the same optimum, and the table of model components contrasts deterministic and stochastic problems.

    View source →

  • Crown and colleagues on choosing the best set of opportunities to fund under a fixed budget

    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. Section 2, Overview of applications of constrained optimization in health care (accepted manuscript), which describes a planner with a number of investment opportunities and a fixed budget inadequate to fund them all, states that choosing the best set to fund under a fixed budget to meet an objective such as maximising total QALYs can be addressed as an optimisation problem, citing Martello and Toth on knapsack problems, and gives vaccination leaving fewer cases to treat as an example of interactions between investments. The abstract's Conclusions state that the methods give decision makers insight into optimal target solutions and the magnitude of the loss of benefit or increased costs associated with the ultimate policy choice.

    View source →

  • Dakin and Tsiachristas on health care allocation as a 0-1 knapsack problem solved by integer programming

    Dakin H, Tsiachristas A. Rationing in an era of multiple tight constraints: is cost-utility analysis still fit for purpose? Applied Health Economics and Health Policy. 2024;22(3):315-329 (author manuscript read in Europe PMC, PMC7615833). Section 2.1, Constrained optimisation, which states that constrained optimisation can allocate resources across a healthcare system to maximise population health conditional on the budget and any other constraints, calls this an integer programming approach that has been adapted for healthcare, and frames the allocation as a 0-1 knapsack problem of choosing which items to pack to maximise value without exceeding a weight constraint or packing more than one of each item. Section 2.2 states that the league table, adopting interventions from the lowest ICER upwards until the budget is exhausted, is equivalent to the greedy algorithm for the knapsack problem.

    View source →

  • Stinnett and Paltiel on mathematical programming beyond restrictive allocation assumptions

    Stinnett AA, Paltiel AD. Mathematical programming for the efficient allocation of health care resources. Journal of Health Economics. 1996;15(5):641-653. Abstract, which states that previous discussions of allocating health care resources subject to a budget constraint relied on unnecessarily restrictive assumptions, that a general mathematical programming framework can accommodate returns to scale, partial and complete indivisibility and programme interdependence, and that methods are presented for incorporating ethical constraints, including explicit identification of the cost of equity.

    View source →

Canonical Identity

Persistent URI
https://healtheconomics.wiki/formula/integer-optimum-of-the-0-1-funding-problem-for-four-indivisible-programmes-with-its-gaps-to-a-funding-rule-and-to-the-divisible-fill

Stable URI · Machine-readable · Resolvable · CC BY 4.0