Robust Linear Programming — Optimization Under Uncertainty
- Introduced by
- Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
- Year
- 1999–2004
- Type
- Uncertainty-robust linear optimization
- Family
- Simulation / optimization
What does it do?
Robust Linear Programming (RLP) extends classical linear programming to handle uncertainty in problem data — cost coefficients, constraint coefficients, or right-hand sides — by requiring solutions to remain feasible and near-optimal across all realizations of uncertain parameters within a defined uncertainty set.
It replaces probabilistic assumptions with worst-case guarantees, making it practical when distributional knowledge is limited.
The intuition behind the method
Ordinary linear programming finds the best solution assuming all data are known exactly. In practice, coefficients are estimated, forecasted, or measured with error. RLP asks: what is the best decision that stays feasible no matter how the uncertain parameters vary within a plausible range? The analyst specifies an uncertainty set — a box, ellipsoid, or polyhedral region — and the solver finds the plan that is optimal for the worst case inside that set. Bertsimas and Sim's budget-of-uncertainty formulation lets the analyst tune conservatism: a parameter Gamma controls how many coefficients are allowed to deviate simultaneously, interpolating between the nominal LP and the fully conservative worst-case.
History
Robust optimization was placed on a firm theoretical footing by Ben-Tal and Nemirovski (1999), who showed that uncertain linear programs with ellipsoidal uncertainty sets yield tractable second-order cone programs. Bertsimas and Sim (2004) introduced the budget-of-uncertainty framework, which keeps the reformulation as a linear program and makes robustness tunable via a single parameter, greatly expanding practical adoption in operations research and engineering.
When to use it
Use RLP when data uncertainty is real but probability distributions are unknown or unreliable, such as in supply chain planning with uncertain demand, energy dispatch with forecast errors, or financial portfolio construction under ambiguous returns. It is appropriate when constraint feasibility under all scenarios is non-negotiable. Avoid RLP when uncertainty is negligible relative to the objective scale, when probability distributions are well-characterized (stochastic programming may be preferable), when the number of uncertain parameters is so large that the robust counterpart becomes intractable, or when the worst-case scenario is unrealistically pessimistic for the application.
Limitations and considerations
- Worst-case orientation can produce overly conservative solutions when extreme scenarios are highly unlikely.
- Ellipsoidal uncertainty sets yield tractable second-order cone programs but no longer pure LPs, increasing solver requirements.
- Requires the analyst to specify an uncertainty set, which is itself a modeling choice that affects results significantly.
- Does not directly provide probability-of-violation statements; stochastic programming is better if tail probabilities matter.
- Degenerates to the nominal LP when Gamma = 0, offering no protection against uncertainty.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Provides hard worst-case feasibility guarantees without requiring distributional assumptions.
- The Bertsimas-Sim budget formulation produces a tractable LP counterpart solvable with off-the-shelf solvers.
- The robustness budget Gamma gives the analyst an intuitive dial to trade off solution quality against conservatism.
- Computationally efficient — robust counterparts for budget sets have similar complexity to the original LP.
- Particularly well-suited to problems where constraint violation is costly or unsafe.
Applications
- Supply chain network design with uncertain transportation costs and demand
- Electric power system dispatch under renewable energy forecast uncertainty
- Portfolio optimization with ambiguous asset return ranges
- Radiation therapy treatment planning with patient motion uncertainty
- Airline crew scheduling under uncertain flight delays
- Water resource allocation with uncertain precipitation and evaporation
How it works
How it works
Formulate the nominal linear program: minimize a linear objective c^T x subject to linear inequality constraints Ax <= b and non-negativity. Identify which coefficients — typically constraint matrix entries a_ij — are uncertain. This step mirrors standard LP modeling but flags each uncertain parameter.
Formula
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0Construct an uncertainty set U that captures the range of plausible parameter values without requiring a probability distribution. Common choices are box sets (each parameter varies independently within [a_bar - a_hat, a_bar + a_hat]), ellipsoidal sets (Ben-Tal and Nemirovski, 1999), and budget sets (Bertsimas and Sim, 2004). The budget parameter Gamma bounds how many parameters can simultaneously take their worst-case values.
Formula
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}Replace each uncertain constraint with its robust counterpart: require feasibility for every realization in U. This transforms the original problem into a semi-infinite program — infinitely many constraints, one per element of U.
Formula
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall iDerive a tractable deterministic equivalent. For budget uncertainty sets the robust counterpart reformulates as a standard LP or mixed-integer LP of similar size, solvable with conventional solvers. The key reformulation introduces auxiliary variables that linearize the inner maximization over the uncertainty set.
Formula
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_iSolve the reformulated LP using a standard solver (simplex or interior-point). Evaluate the solution: check worst-case constraint violation across the uncertainty set, report the price of robustness (the objective increase relative to the nominal LP), and perform sensitivity analysis on the robustness budget Gamma.
Common pitfalls
- Setting Gamma too high makes every constraint worst-case simultaneously, yielding an overly conservative and expensive solution.
- Misspecifying the uncertainty set (e.g., ignoring correlation structure) can lead to either over- or under-protection.
- Confusing robust LP with stochastic LP: RLP maximizes worst-case performance, not expected performance.
- Ignoring the price of robustness report — always compare the robust objective to the nominal LP objective to quantify the conservatism cost.
- Applying RLP to problems with integer variables without switching to the robust mixed-integer formulation, which requires different reformulations.
Frequently asked questions
How does Robust LP differ from Stochastic LP?
Stochastic LP optimizes expected performance given a probability distribution over scenarios, requiring distributional knowledge. Robust LP optimizes worst-case performance over an uncertainty set, requiring only bounds — no probability distribution. Robust LP is preferred when distributions are unreliable; stochastic LP is preferred when they are well-estimated.
What is the price of robustness?
The price of robustness is the increase in objective value (cost) of the robust solution relative to the nominal LP solution. Bertsimas and Sim (2004) proved this price grows only as the square root of the number of uncertain parameters for budget sets, making robustness surprisingly affordable.
What is the robustness budget Gamma?
Gamma is a parameter in the Bertsimas-Sim model that controls how many uncertain coefficients are allowed to simultaneously take their worst-case values. Gamma = 0 recovers the nominal LP; Gamma = n protects against all n parameters deviating at once. Analysts typically choose Gamma based on acceptable violation probability bounds.
Does Robust LP require a special solver?
No. For box and budget uncertainty sets, the robust counterpart is itself a linear program, solvable with any standard LP solver (CPLEX, Gurobi, HiGHS, etc.). Ellipsoidal sets require a second-order cone program solver, which is also widely supported.
When should I use Robust Mixed-Integer Programming instead?
If decision variables must be integer (e.g., binary yes/no decisions, lot sizes), the robust counterpart contains integer variables and becomes a Robust Mixed-Integer Program. The uncertainty-set approach is the same, but the reformulation and solver requirements change accordingly.
Related methods
Sources
Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
Open DOI referenceCopied.Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.
Open DOI referenceCopied.