Uncertainty sets for robust optimization

Question

I have a few questions regarding the Robust Optimization(RO) approach.

I am trying to consider uncertainty in a rhs vector, which is uncertain demand.

First, Im not seeing any different in proposing a box uncertainty set, and just putting the worst-case realization in the optimization, instead of random parameter. Is it ok?

Would you give me guidance for making Ellipsoidal uncertainty sets, from historical data, for my rhs parameter?

I also, after trying but not so sure, think that there is no difference between Ellipsoidal and box sets for my case, if I am to ensure the feasibility for all possible realization.

Maybe, Ellipsoidal sets are advised just for soft constraints?

Answer 1

First question:

"First, Im not seeing any different in proposing a box uncertainty set, and just putting the worst-case realization in the optimization, instead of random parameter

indicates some kind of confusion of how uncertain problems are solved. Once you have the uncertain parameter in the model, and want to solve the robust problem, you have to derive an optimization problem which actually can be solved, and that typically involves explicitly optimizing over the uncertainty set and deriving the worst-case counterpart, which in your case sounds like plugging in the worst-case realization(s).

In other words, yes that is ok, because that is what you have to do typically.

Second question: Finding a minimal volume ellipsoid covering a set of points can be cast as a semidefinite programming problem (A MAXDET problem to be precise)

Whether box and ellipoidal uncertainty is equivalent in your model is impossible for us to answer, as we don't know the specifics of how the uncertainty enters your rhs.

Third question: Ellipsoidal only for soft constraints? No, why would that be the case.

Answer 2

Thank you Johan.

Let me explain the specific case: the uncertain constraint has one scalar rhs, which is uncertain demand at the time level. (Left-hand side is a linear function of an integer decision variable).

This model gives me difficulty to try RO approaches, since it does not seem to be flexible.

I want to solve it via Budget of Uncertainty (Bertsimas) approach, but its only one uncertain scalar for each constraint!

I want to create ellipsoidal uncertainty sets, but how can I create such for 1-D historical data of that scalar ?!