Uncertainty Sets
The uncertainty set is the modeling choice at the heart of robust optimization; its shape controls both conservatism and computational tractability.
The central modeling object
In robust optimization every uncertain parameter is assumed to live in a set U, and the solution must hold for all values in U. The choice of U is the crucial modeling decision: too large and the solution is needlessly conservative; too small and it fails to protect against realistic deviations. The set's geometry also determines what kind of problem the robust counterpart becomes.
Common shapes
A box set treats each parameter's interval independently, which is simple but assumes all worst cases occur simultaneously, the most pessimistic view. An ellipsoidal set bounds a weighted Euclidean distance from a nominal value, capturing correlations and yielding an SOCP counterpart. A polyhedral set is defined by linear inequalities and keeps a robust LP linear. The budgeted set of Bertsimas and Sim caps the number of parameters that may deviate at once.
- Box: axis-aligned intervals, independent, most conservative
- Ellipsoid: Euclidean ball, captures correlation, gives SOCP
- Polyhedron: linear facets, keeps LPs linear
- Budget (Gamma): limits simultaneous deviations, tunable conservatism
The budget parameter
The budgeted set introduces a parameter Gamma controlling how many uncertain coefficients may reach their extreme values at the same time. Setting Gamma to zero gives the nominal problem with no protection; setting it to the full dimension gives box-level worst-case protection; intermediate values interpolate. This gives a single knob to trade guaranteed protection against average performance, with a probabilistic bound on constraint violation tied to Gamma.
Building sets from data
Uncertainty sets can be constructed from data rather than assumed: a confidence region from a statistical estimate, a convex hull of observed samples, or a set calibrated so that the probability of the true value falling outside it is controlled. Data-driven set construction connects robust optimization to distributionally robust optimization, where the uncertainty is over the distribution itself rather than the raw parameter.