Linear & Mixed-Integer Programming for Business Decisions

The last module ended with a decision rule per unit: compute the expected value of each action, pick the best. That works until decisions compete for something. A retention budget of $120k a month. Six hundred account-manager calls. Two warehouses with fixed capacity. A fleet of 40 vans.

Once one decision uses up something another decision needs, choosing the best action for each unit independently is no longer optimal, and often not even feasible. You need mathematical optimization: linear programming (LP) and mixed-integer programming (MIP). They’re decades old, extremely well engineered, and hugely underused by ML teams.

The anatomy of an optimization model

Every optimization model has three parts:

• Decision variables: the quantities you choose. x[c, a] = 1 if customer c gets action a, else 0. Or q[s] = units of SKU s to order.
• Objective: a function of the variables to maximize or minimize. Total expected margin gain.
• Constraints: limits the variables must respect. Budget, capacity, at most one action per customer.

If the objective and constraints are linear in the variables and the variables are continuous, it’s an LP, solvable to proven optimality very quickly even with millions of variables. If some variables must be integers (yes/no, whole units), it’s a MIP, which is much harder in theory but routinely solvable in practice for real business sizes.

The skill that matters isn’t the solver algorithm. It’s formulation: translating the decision spec from Lesson 2 into variables, objective and constraints.

Formulating the retention allocation

From the spec: each customer gets at most one action, the total cost of offers can’t exceed the budget, and account-manager calls are capped at 600. The value of each (customer, action) pair comes from the scoring layer: expected margin gain over doing nothing.

maximize    Σ_c Σ_a  value[c,a] · x[c,a]
subject to  Σ_a x[c,a] ≤ 1                      for each customer c
            Σ_c Σ_a  cost[c,a] · x[c,a] ≤ 120000
            Σ_c x[c, call] ≤ 600
            x[c,a] ∈ {0, 1}, and x[c,a] = 0 if a is ineligible for c

Here it is in OR-Tools, a free, production-grade solver library:

from ortools.linear_solver import pywraplp

def allocate_offers(value, cost, eligible, budget, call_cap):
    """value[c][a], cost[c][a]: dicts from the scoring layer.
    eligible[c]: list of allowed actions after rules (Lesson 16)."""
    solver = pywraplp.Solver.CreateSolver("SCIP")
    solver.SetTimeLimit(60_000)  # ms; always bound solve time in production

    x = {(c, a): solver.BoolVar(f"x[{c},{a}]")
         for c in eligible for a in eligible[c] if a != "none"}

    for c in eligible:  # at most one offer each ("none" is implicit)
        solver.Add(solver.Sum(x[c, a] for a in eligible[c] if a != "none") <= 1)

    solver.Add(solver.Sum(cost[c][a] * v for (c, a), v in x.items()) <= budget)
    solver.Add(solver.Sum(v for (c, a), v in x.items() if a == "call") <= call_cap)

    solver.Maximize(solver.Sum(value[c][a] * v for (c, a), v in x.items()))

    status = solver.Solve()
    if status not in (pywraplp.Solver.OPTIMAL, pywraplp.Solver.FEASIBLE):
        raise RuntimeError(f"no plan found, status={status}")

    plan = {c: "none" for c in eligible}
    for (c, a), v in x.items():
        if v.solution_value() > 0.5:
            plan[c] = a
    return plan, solver.Objective().Value()

A few production habits are already visible here:

• Ineligible actions never get variables. Rules prune the action space before the solver sees it, which keeps the model small and makes policy violations impossible rather than just penalized.
• Only positive-value pairs need variables. If value[c, a] ≤ 0, the solver would never choose it; skip it to shrink the model further.
• Time limits and status checks. A solver that runs forever or returns garbage silently is an outage. Always bound the time, always check status, and when the status is FEASIBLE rather than OPTIMAL, log the optimality gap.

Choosing a solver

OR-Tools wraps several engines. For linear and mixed-integer problems the common choices are:

• HiGHS: open source, very fast for LPs and good for MIPs. Also available through scipy.optimize.milp and linprog.
• SCIP: open source MIP solver, strong on harder combinatorial problems.
• CP-SAT (OR-Tools): a constraint programming solver that excels at scheduling, rostering and problems with lots of logical constraints and integer variables.
• Gurobi / CPLEX / Xpress: commercial solvers, often substantially faster on large or hard MIPs. Worth it when solve time or solution quality is the bottleneck.

Write the formulation once, behind a modeling layer (OR-Tools’ pywraplp, Pyomo, or PuLP), so you can switch solvers without rewriting the model.

Shadow prices: what constraints are worth

Solve the LP relaxation (let x be continuous between 0 and 1 instead of binary) and each constraint comes back with a dual value, also called a shadow price: how much the optimal objective would improve if that constraint were relaxed by one unit.

# Same model with NumVar(0, 1) instead of BoolVar, solved with GLOP (LP).
budget_ct = solver.Add(total_cost <= budget)
...
solver.Solve()
print("value of $1 more budget:", budget_ct.dual_value())
print("value of 1 more call slot:", calls_ct.dual_value())

Shadow prices answer real business questions:

• “Should we increase the retention budget?” If the budget’s shadow price is $1.80, each extra dollar of budget earns $1.80 of margin at the margin. Keep asking for budget until it drops towards $1.
• “Is the call team a bottleneck?” A high shadow price on call capacity says hiring another account manager is worth it.
• “Does this policy cost us money?” Add a policy as a constraint and read its shadow price. A zero means it isn’t binding; a large number tells the business what the rule costs.

For MIPs, duals aren’t defined directly, but the LP relaxation’s duals are usually a good guide, and for large problems the LP and MIP solutions are typically very close.

Scaling: the Lagrangian threshold trick

A batch job with 3 million customers and 5 offers is a MIP with 15 million binary variables. Solvers can sometimes handle that, but there’s a much simpler approach when there’s one coupling constraint, like a single budget.

Put a price λ on the budget. Then each customer can be decided independently: choose the action that maximizes value − λ × cost (or “none” if nothing is positive). Higher λ makes offers more “expensive” and fewer customers get them. Search for the smallest λ whose total spend fits the budget:

import numpy as np

def allocate_with_price(values, costs, budget, iters=50):
    """values, costs: arrays shaped (n_customers, n_actions);
    column 0 is 'none' with value 0 and cost 0. Ineligible pairs
    should already have value -inf."""
    lo, hi = 0.0, 100.0
    for _ in range(iters):  # binary search on the budget's price
        lam = (lo + hi) / 2
        choice = np.argmax(values - lam * costs, axis=1)
        spend = costs[np.arange(len(choice)), choice].sum()
        if spend > budget:
            lo = lam
        else:
            hi = lam
    choice = np.argmax(values - hi * costs, axis=1)
    return choice, hi   # hi: feasible price, approximately the shadow price

This runs in seconds on millions of rows, is nearly optimal when there are many small decisions, and λ comes out as (approximately) the budget’s shadow price. With several coupling constraints, the same idea extends with one price per constraint (Lagrangian relaxation or a primal-dual method).

Carrying the plan into real time

The price trick also solves a recurring production problem: the batch job allocates the monthly budget, but some decisions happen in real time (a customer visits the cancel page). The real-time path can’t re-solve a 3-million-customer MIP in 50 ms.

Instead, the batch job publishes λ. The real-time service picks, for the single customer in front of it, the eligible action maximizing value − λ × cost. Decisions stay consistent with the global plan, the budget is respected on average, and the batch job recomputes λ daily as spend is consumed. If spend runs ahead of plan mid-month, raise λ; if behind, lower it. This is exactly how ad budget pacing and many dynamic pricing systems work.

Optimization is powerful, but it takes its inputs as truth. The next lesson is about what happens when those inputs are predictions, and why the optimizer will find their errors for you.