Gamma uncertainty set

Question

I am new to the concept of robust optimization. I am currently trying to use a gamma uncertainty set (Bertsimas and Sim, 2002) for the following scenario. Suppose we have a constraint of the form $\sum{a_{i,j}} \geq b_j$ for $I \in I, j \in J$ with uncertainty in the rhs. I was interested in finding an answer to the following questions about the gamma uncertainty set:

1. As far as I understood, in the gamma uncertainty set we essentially introduce a set $U$ which keeps track of the constraint coefficients that are subject to parameter uncertainty. Do we need to reformulate the constraint, so $b_j$ is part of the lhs and introduce a variable which corresponds to its coefficient (e.g. $b_{j,u}$ where $u \in U$)?

2. Given that we want to simulate this, we can have gamma as a parameter and we select up to Gamma constraints to be changed. Assuming this is true, how do we decide the actual change to the nominal value so it fits the gamma uncertainty framework?

Answer 1

I think you meant $\sum_{i\in I} a_{i,j} x_i \ge b_j$ for all $j \in J$. In section 14.1 of Bertsimas/Weismantel, Optimization over Integers (2005), your first question is addressed by introducing a new (fixed) variable $x_{n+1}=1$, where $n=|I|$, and rewriting the constraint as $\sum_{i\in I} a_{i,j} x_i - b_j x_{n+1} \ge 0$ so that all the uncertain coefficients appear on the LHS.

For your second question, the uncertainty interval for each coefficient is part of the input. It should be wide enough to capture the worst case in which Nature works against you but not so wide that it includes values that will never occur. If you have historical data, you could apply statistical techniques for estimating the range of a random variable.