Uncertains and robust constraints

A model quantity or coefficient whose value is subject to uncertainty is called an uncertain.

Intuitively, an uncertain can be viewed as a unknown quantity that is not under our control, but is controlled by an opponent. The opponent makes his decision for the values of the uncertains after we have made our decision, i.e., after the solver has found an optimal value for the model variables. Hence, the values of the model variables must assume the worst case.

A model constraint that includes some uncertainty in the form of an uncertain coefficient or right hand side is called a robust constraint. A good way to visualize the concept of robust optimization is to consider a robust constraint as a two-phase expression. For the sake of argument, let us assume a less-than or equal-to constraint that contains some uncertain model quantities:

Here, all a_i coefficients are known. However, the values of coefficients of variables x_k to x_n are only known to some level of uncertainty, denoted by u_k to u_n. As for traditional variables, we must define the values these uncertains can take.

The feasible region of the uncertains is called the uncertainty set, and is modelled by means of constraints on the uncertains. In the example above, we may know that the uncertain quantities are likely to be small and their norm might be bounded from above, hence we want a solution that is robust at a given confidence level. This implies a constraint on the uncertains of the form

Having described the possible values of the uncertains, robust optimization aims to find a solution that is always feasible, thus the robust constraint is equivalent to the constraint

A robust model may contain several robust constraints and several uncertainty sets. The solvability of a robust optimization problem depends on whether the robust constraints in the model can be transformed into a form that can be solved by the available mathematical programming solvers. The resulting transformed model that is solved is called the robust counterpart.