Choosing a technique: from the structure of a problem to a method¶
Every chapter in this book opens its formulation with a short "Why these techniques?" section. This page is the map behind those sections. It answers the question that separates an optimisation engineer from someone who knows solver syntax: given this problem, which method, and why?
The answer almost never comes from the application ("it's a battery problem"). It comes from the structure of the problem: what kind of numbers the decisions are, what shape the objective and constraints have, how big the problem is, what is uncertain and when it is revealed, and what couples the parts together. Get the structure right and the method follows. Choose the method first and the model gets bent to fit it.
Six questions to ask before choosing¶
| # | Question | If the answer is… | …it points to |
|---|---|---|---|
| 1 | Are the decisions continuous, or are some yes/no, lumpy or either/or? | all continuous | LP, QP, convex optimisation |
| some must be whole numbers or switches | MILP: binaries, big-M links, branch and bound | ||
| 2 | Are the objective and constraints linear? Convex? | linear | LP: corners and duals, simplex or interior point |
| convex quadratic | QP; convex in general: conic or convex solvers | ||
| non-convex | local methods with multistart, piecewise-linear MILP approximations, global solvers | ||
| 3 | How many decisions and constraints? | 2 | the graphical method (Chapter 1), for intuition |
| dozens to millions | an algebraic method in a solver: simplex (T0), interior point, first-order | ||
| 4 | What is uncertain, and when is it revealed? | nothing that matters | deterministic optimisation |
| revealed after you commit | two-stage stochastic programming (Chapter 15) | ||
| revealed gradually; you can re-decide | rolling horizon / MPC (Chapter 9), dynamic programming (Chapter 11) | ||
| must hold with a stated probability | chance constraint (Chapter 4) | ||
| the bad tail matters, not just the mean | a risk measure (CVaR) in the objective or constraints (Chapters 13–15) | ||
| only bounds are known, or a guarantee is required | robust optimisation, a budget of uncertainty (Chapter 16) | ||
| a distribution is estimated but cannot be trusted | distributionally robust optimisation (Chapter 16) | ||
| 5 | Does one constraint couple otherwise independent parts? | yes, a budget across days or a commitment across scenarios | decomposition: Lagrangian (Chapter 10), Benders / L-shaped (Chapter 15) |
| 6 | Is it really an estimation problem, or a sharing problem? | fit a model to data | least squares, LAD, maximum likelihood, Kalman filter (T3, Chapters 3, 10) |
| split a gain or a loss fairly between players or factors | Shapley value, the core (Chapters 9, 12, 13) |
Two more questions decide how a method is used in practice:
- How fast must it answer? A 5-minute dispatch cycle tolerates seconds, not hours. That favours LPs, warm starts and decomposition over big MILPs, and makes latency budgets a modelling constraint (production track).
- Who will act on it? An answer that cannot explain which constraint binds and what it is worth (the duals) is hard to defend to an operator, a board or a lender. That is a reason to prefer exact methods with duals over black-box heuristics whenever both are fast enough.
Why linear programming comes first¶
Most operational decisions in this book are continuous quantities (MW, MWh, $) with linear physics and economics: energy balances, capacity limits, revenue equals price × quantity. That makes them LPs, and an LP is the best kind of problem to have:
- Global optimum: an LP has no false local optima. Any optimum the solver reports is the best possible.
- Corners: the optimum sits at a corner of the feasible region. In two dimensions you can see it (Chapter 1). In many dimensions the simplex method walks from corner to corner, moving along an edge whenever that improves the objective (T0; Dantzig, 1963).
- Constraint types:
- a \(\le\) constraint gets a slack variable (unused capacity), which also gives a free starting corner;
- a \(\ge\) constraint gets a surplus plus an artificial variable;
- an \(=\) constraint gets an artificial.
Artificials are removed by the big-M (Charnes, 1952) or two-phase method. If they cannot be removed, the problem is infeasible. Solvers do all of this automatically, but you will read about it in their logs and status codes. - Duals for free: every constraint has a shadow price, the value of one more unit of whatever it limits. The book uses these again and again: - a shared line (Chapters 1 and 12); - a throughput budget (Chapter 10); - a battery's capacity (Chapter 11); - a stress probability (Chapter 14); - a reserve commitment (Chapter 15); - a battery's failure rate in a worst case (Chapter 16). - Speed: HiGHS solves LPs with hundreds of thousands of variables in seconds.
When the problem is not an LP¶
| Structure | Technique | Chapters | Why not just an LP? |
|---|---|---|---|
| Yes/no and lumpy decisions: commit or not, a band price chosen from a list, a 2.5 MWh augmentation block, a crane booked for whole days | MILP, solved by branch and bound (Land and Doig, 1960) | 2, 4, 5, 8, 11, 14 | the LP relaxation can answer "0.4 of a crane", which is meaningless; rounding it can be infeasible or far from optimal |
| Quadratic risk (variance), least-squares fitting | QP / least squares | 14, T3 | variance is quadratic in the decisions |
| Robust fitting or a median | LAD as an LP | T3 | absolute values linearise with two extra variables |
| Hidden state observed with noise, updated over time | Kalman filter (recursive least squares) | 10 | it is estimation, not optimisation over decisions |
| Decisions over time with a state (state of charge, state of health, capacity) | dynamic programming, MPC | 9, 11 | an LP over the whole horizon assumes perfect foresight; DP and MPC give a policy that reacts to what happens |
| Commit now, adapt later | two-stage stochastic programming | 15 | a deterministic plan on the average scenario ignores the rare events that decide the value (the VSS) |
| Uncertain coefficients and a rule that must hold anyway | robust LP (Bertsimas–Sim budget; dual reformulation or cutting planes) | 16 | the nominal LP sits exactly on the limit it was given, so any data error breaks it |
| Tail risk | CVaR (an LP!), not VaR | 13–16 | VaR is not coherent and is hard to optimise. CVaR is coherent and LP-representable (Rockafellar and Uryasev, 2000) |
| One coupling constraint across many blocks | Lagrangian relaxation, Benders | 10, 15 | the monolithic LP still works, but decomposition scales and its multipliers have meaning |
| Fair attribution among interacting factors or owners | Shapley value, the core | 9, 12, 13 | the order in which factors are removed changes a waterfall. Shapley averages over all orders |
| Very large combinatorial problems where exact methods time out | metaheuristics, only as a last resort | (planned) | they give no optimality guarantee and no duals. Exact methods are preferred whenever they solve in time |
How the chapters map to methods¶
| Chapter | The structure that decided it | Method |
|---|---|---|
| 1 | 2 continuous decisions, linear | graphical LP, duals |
| T0 | the same LP, written algebraically | simplex, big-M, two-phase, Bland |
| 2 | 288 intervals coupled by state of charge; no simultaneous charge and discharge | LP, then MILP |
| 3 | failure data with censoring; one replacement age | maximum likelihood, one-dimensional search |
| 4 | weather uncertainty, safety threshold | chance constraint on an ensemble, enumeration, crew MILP |
| 5 | jobs, crews, a crane, spares over days | time-indexed MILP vs greedy |
| 6 | one shared row; the market clears by offer price | ranking (the exact LP solution), offers |
| 7 | covenant thresholds on uncertain cash flow | expected-value derivatives, value of a dollar |
| 8 | ten discrete price bands | LP for volumes, MILP for band design |
| 9 | information arrives over time; no look-ahead | rolling MPC, perfect-foresight bound, Shapley |
| 10 | cycle-depth damage, hidden state, a throughput budget | rainflow, Kalman filter, LP duality, Lagrangian |
| 11 | lumpy augmentation, years, uncertainty | MILP, DP, Monte Carlo backtest |
| 12 | one line, two contracts, two owners | closed form = LP, parametric LP, Shapley/core |
| 13 | no closed-form distribution; tail matters | Monte Carlo, VaR/CVaR, Euler, Kupiec |
| 14 | revenue linear in hedge volumes | least squares, QP, mean–CVaR LP, MILP lots |
| 15 | commit before uncertainty, adapt after | two-stage SP, L-shaped, SAA, CVaR |
| 16 | uncertain coefficients in security rows; little data on joint failures | robust LP (Bertsimas–Sim), cutting planes, risk-based SP, DR-CVaR |
| T1 | one LP, many solvers | backends compared |
| T2 | infeasible, unbounded, tied or ill-posed models | IIS, optimal faces, regularisation |
| T3 | fitting a curve to noisy SCADA | normal equations vs QR vs SVD, gradient methods, LAD |
A worked example of the reasoning¶
The Chapter 15 battery must reserve capacity for a season before it knows any day's prices:
- Decisions: MW reserved and MW of caps (continuous), then each day's dispatch (continuous). There are no yes/no choices, so not a MILP.
- Shape: with the scenarios fixed, every relation is linear, so it is an LP.
- Uncertainty: the prices are revealed after the commitment, and each day then adapts. That is the definition of two-stage with recourse.
- Size: 1,000 days × 144 variables, linked only by the commitment. The extensive LP works (74 s), but the structure invites Benders / L-shaped decomposition (12 s).
- Tail: the board cares about bad days, so add CVaR, which keeps it an LP.
- Trust: the answer is fitted to a sample, so report SAA bounds. It assumes perfect daily recourse, so backtest with a realistic one.
None of those steps mentions batteries. That is the point: the same reasoning chooses the method for a crane schedule, a hedge book or a tram depot.
References¶
The primary sources for this page are listed in Further reading, with each chapter's own sources under its section. Start with: - Bertsimas and Tsitsiklis (1997) for LP and the simplex method; - Wolsey (2021) for MILP; - Boyd and Vandenberghe (2004) for convexity; - Birge and Louveaux (2011) for stochastic programming; - the MO-book (Postek, Zocca, Gromicho and Kantor, 2025) for the "one problem, many techniques" style this book follows.