Robust Optimisation: Equality vs Inequality constraint (Fixed vs Uncertains)

Hi Will,

the short answer is: your uncertainty set is too large.

First, recall that a robust constraint must be satisfied for all values of the uncertain parameter within the uncertainty set. If u is an uncertain parameter between 0 and 1 and x is a variable, then for the robust constraint

(1+u) x <= 5

to be satisfied for all values of u, it must be x <= 5 / max{(1+u): u in [0,1]} = 5/2. This creates an upper bound for x and allows us to drop the robust constraint (but retain the bound of 1/2 on x). Note that the problem at the denominator attains its optimum for u=1.

The robust constraint

(1+u) x >= 1

is instead equivalent to a new lower bound on x, because x >= 1 / min{(1+u): u in [0,1]} = 1, because x must be >= 1 for the robust constraint to be satisfied for any value of u (note that this time the optimal value of u is 0 instead). The crucial point here is that if both constraints are in the problem, they can both be dropped but x has a bound interval of [1, 5/2], even though these limits correspond each to a different value of the uncertain parameter: one for each of the two robust constraints. It is a defining feature for the robust optimization module that two robust constraints correspond to different values of the uncertain parameters that they use.

For all t, your model uses the same uncertain parameter P23UNCERTAIN(t) over four constraints. For the first two:

P23MODL1 := sum(t in VARIABLES1) (P23COEFF(t)+P23UNCERTAIN(t))*OPTS(t) >= P23TARGETL

P23MODL2 := sum(t in VARIABLES1) (P23COEFF(t)-P23UNCERTAIN(t))*OPTS(t) >= P23TARGETL

the coefficient of OPTS(t) can be low or high depending on P23UNCERTAIN(t). The data file has P23PERCENT(t) positive for all t but P23COEFF(t) sometimes positive, sometimes negative. All uncertain parameters are unbounded from below, therefore all of these uncertain parameters have an interval of [-inf, a(i)]. This implies that even one such constraint makes the problem infeasible: just make all a(i) a sufficiently large negative number for all coefficients of OPTS(t) to be small positive numbers, and the P23TARGETL will never be attained.

A similar conclusion can be drawn for the other two constraints, where a(i) just need to be made negative so that the coefficients on OPTS(t) are negative and hence OPTS(t) obtains a negative upper bound, incompatible with its lower bound of 0.

This could be mitigated by adding a lower bound to all P23UNCERTAIN(t), but a quick test shows that the problem remains infeasible even with bounds as tight as follows:

P23UNCERTAIN(t) <= P23PERCENT(t) * P23COEFF(t)

P23UNCERTAIN(t) >= P23PERCENT(t) * P23COEFF(t) - 0.001

I am not sure of the meaning of such parameters so I don't know if such small value would make sense. If it is indeed very small, consider defining an uncertainty set where all uncertains have both a lower and upper bound AND, for example, a weighted sum of them is bounded from above, or perhaps more suited for this example, the "cardinality" robustness constraint.

Hi Will,

The box uncertainty set you have defined is a sensible approach, but there are a few reasons why you get an infeasible problem.

First, the lower and upper bound should be used within the same constraint, as otherwise the problem becomes “too robust”, i.e. too strong constraints on the mpvars for the solution to be feasible for all uncertain assignments. Rather than writing two constraints with a different sign on the uncertain parameter and only an upper bound on the uncertain itself, I’d rather write one robust constraint and set bounds on the uncertain parameters, i.e. the following uncertainty set:

P23UNCERTAIN(t) <=  P23PERCENT(t) * abs(P23COEFF(t))
P23UNCERTAIN(t) >= - P23PERCENT(t) * abs(P23COEFF(t))

(note the abs() in order to make P23UNCERTAIN(t) vary between a small negative and a small positive) and the following single robust constraint (which replaces the first two with P23TARGETL):

P23MODL1 := sum(t in VARIABLES1) (P23COEFF(t) + P23UNCERTAIN(t))*OPTS(t) >= P23TARGETL

The second pair of constraints would be replaced by a similar single robust constraint. This reflects your box-constrained uncertainty set: the coefficient of OPTS(t) can vary between P23COEFF(t) * (1 – P23PERCENT(t)) and P23COEFF(t) * (1 + P23PERCENT(t)).

I haven’t tried this approach, so I don’t know if it results in an infeasible problem, which anyway depends on your data. The bottom line is that your initial model is infeasible because the robust constraints depend on a very large uncertainty set with due to loose bounds on the uncertain parameters. The above constraints should achieve the robustness you had in mind: the uncertainty set is now a bounded box, but this doesn’t mean the problem is going to be feasible.

Second, the size of the uncertainty set determines how robust the solution will be. The larger the uncertainty set, the more stringent constraints the solution will have to satisfy in order to achieve robustness; this can lead to worse objective function values (because the set of feasible OPTS(t) is more restricted) or even to infeasibility.

Box uncertainty sets have the peculiarity that the uncertain parameters realized at an optimal solution of the robust problem are a vertex of the box, i.e. they are all at their lower or upper bound. This is a rather unlikely practical situation where ALL parameters are far from their expected value. One could imagine only a few such parameters are off. In your case you could also imagine a confidence ellipsoid containing all uncertain realizations, something of the form

sum(t in VARIABLES1) ((P23UNCERTAIN(t) / (abs(P23COEFF(t)) * P23PERCENT(t)))**2) <= 1

which is an ellipsoid contained in the aforementioned box (this would hence replace the upper/lower bound constraints on P23UNCERTAIN(t)) and that prevents all uncertain parameters from being at an extreme of the box (obviously, only use it if this makes sense for your application).

(Note: in Mosel I believe the ** should be replaced by a caret, but the caret i not accepted in text by this forum platform.)

An alternative to the above ellipsoid that limits the (weighted) l-2 distance is an uncertainty set that limits the l-1 distance, and it’s the cardinality() uncertainty set mentioned in the manual.

Hope this helps.

Hi Pietro,

This is excellent and give me a great insight into the issue. Thank you so much for taking the time. I will apply your suggestions.

All the best,

Will.