Robust Linear Programming — Optimization Under Uncertainty
Also known as: RLP, Robust LP, Tractable Robust LP, Uncertainty-Set LP
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.
Key highlights
- 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.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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.
Strengths & limitations
- 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.
- 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.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
- 2.Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Robust Linear Programming. ScholarGate. https://scholargate.app/simulation/robust-linear-programming