Introduction

1. Robust Linear Programming:

   Robust Linear Programming addresses linear programming problems where the data is uncertain, and a solution which remains feasible despite that uncertainty, is sought.

   The robust counterpart to an LP is not an LP in general, but is always convex. The figure on the left illustrates the feasible set of the “robust counterpart” of an LP after we take into account uncertainty in the facets’ directions.

2. Uncertainty Models:

   We have three models for Tractable cases of uncertainty:

   1. Scenario uncertainty
   2. Box uncertainty
   3. Ellipsoidal uncertainty

Tractable Cases

1. Scenario Uncertainty:

   • Uncertainty model: In the scenario uncertainty model, the uncertainty on a coefficient vector a is described by a finite set of points:

   \[\mathbf{U} = \left\{ a^1, \ldots, a^K \right\},\]

   where each vector \(a^k \in \mathbf{R}^n, k=1, \ldots, K\) corresponds to a particular “scenario”.

   • The robust counterpart to a half-space constraint:

   \[\forall \: a \in \mathbf{U} , \;\; a^Tx \le b ,\]

   can be simply expressed as a set of \(K\) affine inequalities:

   \[(a^k)^Tx \le b, \;\; k= 1, \ldots, K.\]

   Note that the scenario model actually enforces more than feasibility at the “scenario” points \(a^k\).

   In fact, for any \(a\) that is in the convex hull of the set \(\mathbf{U}\), the robust counterpart holds.

   Indeed, if the above holds, then for any set of nonnegative weights \(\lambda_1, \ldots, \lambda_K\) summing to one, we have

   \[\sum_{k=1}^K \lambda_k (a^k)^Tx \le b, \;\; k= 1, \ldots, K.\]

   \[\implies\]

   • The robust counterpart to the original LP:

   \[\min_x \: c^Tx ~:~ \forall \: a_i \in \mathbf{U}_i , \;\; a_i^Tx \le b_i , \;\; i= 1, \ldots, m,\]

   with \(\mathbf{U}_i = \{ a_i^1, \ldots, a_i^{K_i} \}, i= 1, \ldots, m,\) becomes

   \[\min_x \: c^Tx ~:~ (a_i^k)^Tx \le b_i, \;\; k=1, \ldots, K_i, \;\; i= 1, \ldots, m,\]

   where this is an LP, with a total of \(K_1+...+K_m\) constraints, where \(K_i\) is the number of elements in the finite set \(\mathbf{U}_i\), and \(m\) is the number of constraints in the original (nominal) LP.

   • The scenario model is attractive for its simplicity. However, the number of scenarios can result in too large a problem.

2. Box Uncertainty:

   • Uncertainty model: The box uncertainty model assumes that every coefficient vector \(a_i\) lies in a “box”, or more generally, a hyper-rectangle \(\in \mathbf{R}^n\), but is otherwise unknown.

   • In its simplest case, the uncertainty model has the following form:

   \[\mathbf{U} = \left\{ a ~:~ |a-\hat{a}|_\infty \le \rho \right\},\]

   where \(\rho \ge 0\) is a measure of the size of the uncertainty, and \(\hat{a}\) represents a “nominal” vector.
   This describes a “box” of half-diameter \(\rho\) around the center \(\hat{a}\).

3. Asynchronous: \

4. Asynchronous: \

5. Asynchronous: \

6. Asynchronous: \

7. Asynchronous: \

8. Asynchronous: \

THIRD

1. Asynchronous: \

2. Asynchronous: \

3. Asynchronous: \

4. Asynchronous: \

5. Asynchronous: \

6. Asynchronous: \

7. Asynchronous: \

8. Asynchronous: \