Optimization Foundations

Module 3: Constrained Optimization and Resource Allocation Depth: Foundation | Target: ~2,500 words

Thesis: Optimization formalizes the question “what is the best we can do given what we have?” and reveals that most organizations optimize implicitly and poorly.

The Operational Problem

Every healthcare organization allocates resources. Nurses are assigned to units. Providers are scheduled across clinic sites. Grant dollars are distributed across program areas. Beds are allocated to service lines. These decisions happen daily, and they are consequential — a misallocated provider-hour in a rural health network is not a rounding error, it is a patient who did not receive care.

The problem is not that these decisions are unmade. The problem is that they are made without formalization. A regional health director distributing five traveling providers across eight clinic sites is solving an optimization problem whether she knows it or not. The question is whether she is solving it well. If the allocation follows last year’s pattern, or a political compromise, or the loudest clinic manager’s demand, she is optimizing — but against an implicit and probably wrong objective, subject to constraints she has not examined, producing an outcome she cannot prove is good, let alone best.

Optimization theory, the branch of operations research concerned with finding the best feasible solution to a formally stated problem, exists precisely to make these decisions explicit, examinable, and improvable. It does not replace judgment. It structures judgment so that the tradeoffs are visible and the reasoning is auditable.

What Optimization Means Formally

An optimization problem has three components:

  1. Decision variables — the things you control. How many provider-days to assign to each clinic site. Whether to open or close a satellite location. How many FTEs to allocate to each program area. Decision variables are the levers.

  2. An objective function — a single quantity you want to maximize or minimize, expressed as a function of the decision variables. Maximize total patient encounters. Minimize total travel time. Maximize weighted patient access where weights reflect acuity or equity priorities. The objective function is what “best” means, made precise.

  3. Constraints — conditions the solution must satisfy. Each clinic must have at least two provider-days per week. Total provider-days cannot exceed 25 (five providers times five days). No provider can be assigned to more than three sites (to limit travel burden). Budget cannot exceed the grant award. Constraints define the boundary between feasible and infeasible.

Together, these three components produce a mathematical program — not a computer program, but a formal statement of a decision problem. The solution is the set of decision variable values that optimizes the objective function while satisfying every constraint. If no such values exist, the problem is infeasible — the constraints are mutually contradictory, which is itself valuable information. If the problem has a solution, that solution is provably the best achievable outcome within the stated constraints.

This is the core contribution: optimization does not just find a good answer. It finds the best answer, or proves that the constraints make any answer impossible. No amount of experience, intuition, or committee deliberation can guarantee either of these outcomes.

Why Formulation Is the Hard Part

George Dantzig, who developed the simplex method for linear programming in 1947 while working on logistics planning for the U.S. Air Force, reportedly spent far more time formulating problems than solving them. This is not a historical curiosity. It is the central truth of applied optimization.

The mathematics of solving a well-formulated optimization problem is settled. The simplex method, interior-point methods, branch-and-bound algorithms — these are implemented in commercial solvers (CPLEX, Gurobi, open-source alternatives like HiGHS) that can handle problems with millions of variables. The solver is not the bottleneck.

The bottleneck is formulation: deciding what to optimize, what constraints are real versus assumed, and what simplifications preserve the problem’s essential structure. Consider a health system deciding how to staff its rural clinics. The formulation questions are harder than they appear:

  • What is the objective? Maximize patient encounters? Maximize geographic coverage? Minimize the maximum wait time at any site? Minimize total cost? Each choice produces a different optimal solution. The math does not tell you which objective is right. That is a values decision, and it must be made explicitly.

  • What are the real constraints? “Each site needs a provider” sounds like a constraint, but is it? Some sites might be better served by telehealth. “Providers can work five days a week” is a legal and contractual constraint. “Provider X always goes to Site A on Tuesdays” may be habit masquerading as a constraint. Every false constraint shrinks the feasible region and excludes potentially superior solutions.

  • What are you ignoring? Travel time between sites. Provider skill mix (a psychiatrist and a family medicine physician are not interchangeable). Patient preferences. Seasonal demand variation. Every omission is a modeling choice with consequences.

The practitioner who can translate an operational mess into a clean formulation — one that captures the decisions that matter, the objective that reflects organizational values, and the constraints that are genuinely binding — is doing the most valuable work in the optimization process. The solver does the rest.

Linear Programming: The Geometry of Constrained Decisions

Linear programming (LP) is the foundation of optimization theory. An LP has a linear objective function and linear constraints — meaning the objective and every constraint are sums of decision variables multiplied by constants, with no squares, products, or other nonlinearities.

The geometric intuition is powerful and worth understanding even if you never solve an LP by hand. Each constraint defines a half-space — a region on one side of a flat boundary. The intersection of all constraint half-spaces is the feasible region, a convex polyhedron (in two dimensions, a polygon; in higher dimensions, a polytope). Every point inside this region satisfies all constraints. Every point outside violates at least one.

The objective function defines a direction — the direction of improvement. Maximizing revenue pushes the solution in one direction; minimizing cost pushes it in another. The optimal solution lies at a vertex (corner point) of the feasible region. This is Dantzig’s fundamental insight: you do not need to search the entire feasible region. You only need to check the vertices. The simplex method does exactly this — it walks from vertex to adjacent vertex, always improving the objective, until no further improvement is possible. At that point, the current vertex is optimal.

For healthcare operators, the geometric picture conveys something important: constraints shape the solution. Adding a constraint cuts away part of the feasible region and may force the optimal solution to a different, worse vertex. Removing a constraint expands the feasible region and may reveal a better solution. This is why examining whether each constraint is real and necessary is not academic fastidiousness — it directly determines how good your best possible outcome can be.

The shadow price of a constraint (also called the dual value) quantifies exactly how much the objective function would improve if that constraint were relaxed by one unit. If the shadow price on the “total provider-days available” constraint is 12 patient encounters per provider-day, then hiring one additional provider-day would generate 12 more encounters. If the shadow price on the “minimum two days at Site C” constraint is -8, then that political commitment is costing eight encounters elsewhere in the network. Shadow prices make the cost of constraints visible, which is essential for operators negotiating resource levels with funders or boards.

Integer Programming: When Decisions Are Discrete

Linear programming assumes decision variables are continuous — you can assign 2.7 provider-days to a site, or allocate $47,312.18 to a budget line. Many real decisions are not continuous. You hire a provider or you do not. You open a clinic site or you do not. You assign a specific person to a specific location on a specific day. These are binary or integer decisions, and they require integer programming (IP) or mixed-integer programming (MIP), where some or all variables are restricted to integer values.

This restriction has severe computational consequences. LP problems are solvable in polynomial time — the simplex method is efficient in practice, and interior-point methods have proven polynomial worst-case bounds (Karmarkar, 1984). Integer programming is NP-hard. There is no known algorithm that solves all IP problems efficiently. The standard approach, branch-and-bound (Land and Doig, 1960), systematically explores possible integer solutions by solving a tree of LP relaxations, pruning branches that cannot improve on the best known solution. Modern solvers are remarkably good at this — they exploit problem structure, apply cutting planes (Gomory, 1958), and use heuristics to find good solutions fast — but large IP problems can still take hours or prove intractable.

For healthcare operations, integer programming is not optional. The most important allocation decisions are discrete:

  • Staffing: Assign provider X to site Y on day Z (binary: yes or no)
  • Facility decisions: Open or close a satellite clinic (binary)
  • Program funding: Fund this program component or not (binary, under a knapsack constraint where total cost cannot exceed the grant budget)
  • Shift design: A nurse works an 8-hour or 12-hour shift (integer choice), and minimum staffing must be met in every time period

The knapsack problem deserves specific mention because it maps directly to budget allocation under grant constraints. Given a fixed budget (the knapsack capacity) and a set of potential investments each with a cost and a projected benefit, which combination of investments maximizes total benefit without exceeding the budget? This is a textbook IP problem, and it arises every time a grant program manager decides which activities to fund within a fixed award. Solving it by intuition reliably underperforms solving it with a model, because humans are poor at evaluating combinatorial tradeoffs — there are 2^n possible subsets of n candidate investments, and the best combination is rarely obvious.

Multi-Objective Optimization: Making Tradeoffs Visible

Healthcare rarely has a single objective. Access competes with cost. Throughput competes with quality. Geographic equity competes with operational efficiency. Coverage competes with depth of service. Optimizing one objective while ignoring others produces solutions that are technically optimal and operationally unacceptable.

Multi-objective optimization addresses this by finding the Pareto frontier — the set of solutions where no objective can be improved without worsening another. The concept originates with Vilfredo Pareto’s work on economic efficiency (1896) and was formalized for optimization by Harold Kuhn and Albert Tucker’s work on necessary conditions for optimality with multiple constraints (the Karush-Kuhn-Tucker conditions, 1951).

A solution is Pareto optimal (or Pareto efficient) if there is no other feasible solution that is at least as good on every objective and strictly better on at least one. The Pareto frontier is the collection of all such solutions. Points below the frontier are dominated — you could do better on at least one objective without sacrificing anything. Points beyond the frontier are infeasible.

For an operator, the Pareto frontier transforms the conversation from “what is the best answer?” to “what tradeoff do we want to make?” Consider a rural health network balancing patient access (measured in encounters per week) against cost (total provider compensation plus travel). The Pareto frontier might show:

  • High-access solution: 420 encounters/week at $185,000/month — every site staffed every day, maximum travel
  • Low-cost solution: 280 encounters/week at $110,000/month — providers concentrated at highest-volume sites, minimal travel
  • Frontier between them: a curve of solutions where each additional 10 encounters costs progressively more, because they come from staffing increasingly remote, low-volume sites

The shape of this curve is operationally diagnostic. A steep section means large access gains for modest cost increases — low-hanging fruit. A flat section means you are paying heavily for marginal access. The frontier does not make the decision. It makes the decision legible.

Healthcare Example: Provider Assignment in a Rural Health Network

Cascade Rural Health Network (a composite based on published network optimization studies and typical Pacific Northwest configurations) operates eight clinic sites across three counties, served by five traveling providers — three family medicine physicians and two nurse practitioners. Each provider works five days per week. Sites range from a critical access hospital outpatient clinic (Ridgeview, population catchment 8,200) to a part-time satellite clinic in a town of 900 (Elk Prairie). The network receives HRSA funding with a requirement to maintain minimum access at all designated service sites.

Formulation as an assignment problem:

  • Decision variables: x_ij = number of days per week provider i is assigned to site j (integer, 0 to 5)
  • Objective: Maximize total weighted patient encounters, where the weight for each site reflects unmet need (inverse of current access level times population)
  • Constraints:
    • Each provider works exactly 5 days: sum over j of x_ij = 5 for each provider i
    • Each site receives at least 1 provider-day per week (HRSA minimum access requirement)
    • Ridgeview (the critical access hospital site) receives at least 3 provider-days (volume requirement)
    • No provider is assigned to more than 3 sites (travel burden limit)
    • NPs cannot be the sole provider at sites requiring physician oversight for specific procedures
    • Total travel cost does not exceed $4,200/week (fleet budget)

This is a mixed-integer program. Solving it reveals several things the network’s current schedule — built by the medical director over coffee based on provider preferences and historical patterns — does not:

  1. Elk Prairie is overstaffed relative to its weighted need. The current schedule sends a provider two days per week because the previous medical director lived nearby. The optimal solution assigns one day, freeing a provider-day for Cedar Falls, which has three times the unmet need.

  2. The travel budget is not binding. The shadow price on the travel budget constraint is zero — the current budget is not what limits access. The binding constraint is provider-days. One additional provider would increase weighted encounters by 18%, while a 20% increase in the travel budget would change nothing.

  3. The physician-oversight constraint costs 6% of total encounters. Relaxing it — by expanding NP scope of practice or adding telehealth physician supervision — would allow NPs to cover sites currently requiring a physician on-site, unlocking a materially better allocation.

These findings are invisible without formalization. The medical director’s schedule is not bad — it is a reasonable heuristic solution. But it is demonstrably not optimal, and the gap between the heuristic and the optimum translates to patients who could be seen but are not.

The Implicit Optimization Problem

Every resource allocation is an optimization — the question is whether it is a good one. When a health system allocates by precedent (“same as last year”), by politics (“the board member wants that clinic open five days”), or by squeaky wheel (“that site manager calls me every week”), it is solving an optimization problem with an implicit objective function (minimize complaints, preserve relationships, avoid disruption) and implicit constraints (including many that are not real constraints at all, just habits).

This is not a moral failing. It is a structural one. Humans solving combinatorial allocation problems by intuition systematically leave value on the table — Herbert Simon’s concept of satisficing (1956) describes exactly this behavior. We find a feasible solution that seems acceptable and stop searching, because the space of alternatives is too large to evaluate mentally. Optimization models search the entire feasible space. The gap between the satisficing solution and the true optimum is the optimization gap, and in healthcare resource allocation, it routinely represents 10-25% of achievable performance, based on published studies of nurse scheduling, surgical suite utilization, and clinic network design.

Limitations and Failure Modes

Optimization is powerful precisely because it is formal, and it fails precisely when the formalization misrepresents reality.

Garbage in, garbage out. An optimization model with wrong demand estimates, wrong cost parameters, or wrong capacity figures will produce a confidently wrong answer. The model’s output is only as good as its inputs, and in healthcare, data quality is often poor — patient volume figures may exclude no-shows, cost figures may not include overhead, and capacity estimates may assume full productivity from providers who spend 30% of their time on documentation.

Political constraints are real constraints. A model that says “close Elk Prairie” may be mathematically optimal and politically suicidal. The HRSA grant may require maintaining all designated service sites. The county commissioner may sit on the hospital board. These constraints are not in the linear program, but they bind the solution in practice. The sophisticated operator uses the model to quantify what political constraints cost — “maintaining Elk Prairie at two days per week costs the network 14 encounters per week at other sites” — and then makes the political decision with that cost visible.

Optimizing the wrong objective. The most dangerous failure mode is a well-solved problem with a wrong objective function. Maximizing patient encounters (volume) when you should be maximizing access equity (distribution) produces a solution that concentrates providers at high-volume sites and abandons low-volume, high-need communities. Minimizing cost when you should be maximizing quality-adjusted outcomes produces a cheap, ineffective system. The model optimizes exactly what you tell it to optimize. If you tell it the wrong thing, it will find the best possible wrong answer.

Static models in dynamic systems. A single-period optimization that allocates resources based on average demand ignores seasonality, flu surges, provider absences, and the stochastic nature of patient arrivals. The optimal allocation for average Tuesday may be badly wrong for the Tuesday after Thanksgiving. Robust optimization and stochastic programming (Birge and Louveaux, 1997) address this, but at the cost of increased model complexity and data requirements.

Product Design Implications

Software supporting resource allocation decisions should:

  • Surface the implicit optimization. Show operators what their current allocation achieves relative to what a model suggests is achievable. The gap is the product’s value proposition.
  • Make constraints editable. Let operators add, remove, or relax constraints and immediately see how the optimal solution changes. This is scenario planning through constraint manipulation.
  • Display shadow prices in operational language. Not “the dual value of constraint 7 is 12.3” but “one additional provider-day is worth 12 encounters; relaxing the Elk Prairie minimum from 2 to 1 day frees capacity worth 8 encounters elsewhere.”
  • Show the Pareto frontier for multi-objective problems. Let operators slide along the access-vs.-cost tradeoff curve and see which sites gain or lose at each point.
  • Flag when inputs are stale or uncertain. An optimization result based on demand data from 18 months ago should carry a visible warning.

Early Warning Metrics

The metric that reveals degradation earliest is constraint tightness trending toward infeasibility. When the gap between available capacity and minimum coverage requirements narrows — when the slack in the system’s binding constraints approaches zero — the system is approaching a point where no feasible allocation exists. At that point, something must give: a constraint will be violated (a site goes unstaffed), or the objective will degrade sharply. Monitoring constraint slack, not just the objective value, gives operators lead time before the system breaks.

A secondary signal is shadow price volatility. When the marginal value of a resource swings sharply between planning periods, it indicates that the system’s constraints are shifting in ways the current allocation cannot absorb smoothly. Stable shadow prices mean the system is in a regime where small perturbations produce small changes. Volatile shadow prices mean the system is near a tipping point where the binding constraint set is about to change — a different constraint becomes the bottleneck, and the entire optimal solution restructures.

Integration Hooks

Public Finance Module 6 (Financial Controls and Scenario Planning): Grant budget allocation is a constrained optimization problem — specifically, a variant of the knapsack problem where the budget is the capacity, program activities are the items, and projected outcomes are the values. The shadow price on the budget constraint is the marginal value of one additional grant dollar, which is the number a program manager needs when negotiating carryover or supplemental funding.

Workforce Module 6 (Workforce Economics and Capacity Planning): Every variable in a staffing optimization model — provider cost, productivity rate, availability, skill category — comes from workforce data systems. An optimization model that treats all providers as interchangeable, or that uses budgeted rather than actual productivity, will produce solutions that are optimal on paper and infeasible in practice. The workforce module provides the ground truth that the optimization model consumes.