Scenario models
Box uncertainty models
Ellipsoidal models
Scenario uncertainty
Uncertainty model
In the scenario uncertainty model, the uncertainty on a coefficient vector is described by a finite set of points:
where each vector , corresponds to a particular “scenario”.
The robust counterpart to a half-space constraint:
can be simply expressed as a set of affine inequalities:
Note that the scenario model actually enforces more than feasibility at the “scenario” points . In fact, for any that is in the convex hull of the set , the robust counterpart holds. Indeed, if the above holds, then for any set of nonnegative weights summing to one, we have
With a scenario uncertainty, the robust counterpart to the original LP:
with , , becomes
This is an LP, with a total of constraints, where is the number of elements in the finite set .
The scenario model is attractive for its simplicity. However, the number of scenarios can result in too large a problem.
|
A robust half-space constraint with scenario uncertainty, with three scenarios. The constraint represents a polyhedron (dark blue).
|
Example: Robust LP solution to the drug production problem.
Box uncertainty models
Definition
The box uncertainty model assumes that every coefficient vector lies in a ‘‘box’’, or more generally, a hyper-rectangle in , but is otherwise unknown. In its simplest case, the uncertainty model has the following form:
where is a measure of the size of the uncertainty, and represents a ‘‘nominal’’ vector. This describes a ‘‘box’’ of half-diameter around the center .
Note that the robust counterpart to a half-space constraint
can be handled as a scenario model, with “scenarios” the vectors , where represents one of the vertices of the unit box (that is, vectors with 's as components). Indeed, enforcing the constraint implies that holds for every in the convex hull of the 's, which is precisely the box . This approach is not practical, as there are an exponential number of vertices, hence of constraints, to deal with.
Robust counterpart: LP formulation
The robust counterpart is better handled after one realizes that the robust counterpart constraint above is equivalent to
The maximization problem has a simple form (proof):
|
A robust half-space constraint with box uncertainty, with different uncertainty levels. Such sets can be described by a finite (but exponential in the dimension) number of inequalities.
|
With a box uncertainty model, defined as , , the robust counterpart to the original LP:
is also an LP (in polyhedral form)
Ellipsoidal uncertainty
Form of the model
The ellipsoidal uncertainty model has the form
where is a matrix which describes the “shape” of the ellipsoid around its center, which is . If for some , then the above is a simple sphere of radius around ; we refer to this special case as the spherical uncertainty model.
Ellipsoidal uncertainty models are useful to “couple” uncertainties across different components of the coefficient vector . This is contrast with the previous ‘‘box’’ models, which allow uncertainties to take their largest values independently of each other.
Robust counterpart: SOCP formulation
With an ellipsoidal model the robust counterpart is
where we have exploited the Cauchy-Schwartz inequality. (See also here.)
|
A robust half-space constraint with spherical uncertainty, with different uncertainty levels.
|
With an ellipsoidal uncertainty model, defined as , , the robust counterpart to the original LP:
becomes an SOCP:
|