| # Tractable Cases Robust LP > Motivations and standard forms | Tractable cases | Applications 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)
| A robust LP with box uncertainty. The robust feasible set (darker blue) is inside the feasible set for the nominal LP (lighter blue); both feasible sets are polyhedral. The objective is to minimize , where the vector is shown. The nominal LP has many optimal points (red line), which means a solution might be very sensitive to data changes (such as if we change the direction of the objective slightly). Although in this case, the roubst LP has a unique solution (red dot), it is still an LP, so it might be sensitive to changes in the objective vector.
## 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:
| A robust LP with spherical uncertainty. The robust feasible set (darker blue) is inside the (polyhedral) feasible set for the nominal LP (lighter blue). The objective is to minimize , where the vector is shown. The nominal LP has many optimal points (red line), which means a solution might be very sensitive to data changes (such as if we change the direction of the objective slightly). In constrast, the solution to the robust LP is unique (red dot), irrespective of the choice of the objective. As a result, it not very sensitive to changes in the objective or other problem data.