19 - Robust optimization: theory and tools

Summary

Introduction to robust optimization

In many optimization models the inputs to the problem are not known at the time the problem must be solved, are computed inaccurately, or are otherwise uncertain. Since the solutions obtained can be quite sensitive to these inputs, one serious concern is that we are solving the wrong problem, and that the solution we find is far from optimal for the correct problem.

Robust optimization refers to the modeling of optimization problems with data uncertainty to obtain a solution that is guaranteed to be “good” for all or most possible realizations of the uncertain parameters. Uncertainty in the parameters is described through uncertainty sets that contain many possible values that may be realized for the uncertain parameters. The size of the uncertainty set is determined by the level of desired robustness.

Robust optimization can be seen as a complementary alternative to sensitivity analysis and stochastic programming. Robust optimization models can be especially useful in the following situations:

• Some of the problem parameters are estimates and carry estimation risk.

• There are constraints with uncertain parameters that must be satisfied regardless of the values of these parameters.

• The objective function or the optimal solutions are particularly sensitive to perturbations.

• The decision-maker cannot afford to take low-probability but high-magnitude risks.

Recall from Chapter 1 that there are different definitions and interpretations of robustness; the resulting models and formulations differ accordingly. In particular, we can distinguish between constraint robustness and objective robustness.