Robust optimization

Robust optimization is a label that has been attached to a fairly wide variety of optimization modeling frameworks. A rather confusing feature is that “robust” may refer to our inability to represent uncertainty reliably within a probabilistic framework; alternatively, “robust” may refer to decision-makers’ attitude towards risk taking. In this section we mainly refer to the first meaning, which essentially questions the reliability of probability distributions used in making decisions. Sometimes, all we know about uncertain parameters is that they are bounded to lie in a certain region. For instance, we could say that a certain quantity β is not smaller than 5 and not larger than 15, but we are not able to say if the distribution on that support is uniform, beta, triangular, or whatever. Some values of these parameters could be particularly nasty, but even if we know that this is an unlikely occurrence, we do not want to rely on this; on the one hand, we may feel uncomfortable in estimating small probabilities; on the other hand, ethical reasons may prevent us from accepting a solution that could prove a disaster, even with a negligible probability.

All of this is problematic in terms of optimality, but even more so in terms of feasibility. Quite often, one would want to find a solution that is feasible even in the worst possible setting of the parameters, as well as good enough. One way of formulating the problem is the following. Consider a function f(x, β), where x ∈ S is the usual vector of decision variables, which should stay within the feasible set S. The vector β represents a vector of uncertain parameters, which are bounded by a set Ω. Note that we do not characterize this uncertainty in probabilistic terms. Then we can formulate the worst-case optimization problem as

You may interpret the problem as a sort of game between you and Nature. You choose x in order to minimize cost and then, given your choice, she will choose the worst β for you. What you should do is anticipating her nasty behavior by finding a robust solution. Solving a problem like (13.34) requires methods which are quite outside the scope of this book,²⁶ and we refer the reader to the listed references. This may lead to an overly expensive solution, which is usually referred to as fat solution. A chance-constrained approach can be used to enforce a reasonable degree of reliability, but we have already discussed the hidden dangers in this choice. Whether this is in fact an issue depends on the problem at hand and on what is at stake: A few bucks or human lives?

A possible intermediate approach is based on the idea of assuming a probabilistic framework, but relying on a set of probability measures, rather than just one. Denoting by P the set of plausible probability measures, we may tackle the following problem:

where  denotes the expectation under a probability measure  within the set P. Again, this typically results in an intractable problem that can be suitably approximated by numerical techniques.