What is robust optimization?

Question

What is the academic definition of robust optimization? What are examples of robust optimization on:

• shift rostering
• vehicle routing problem
• facility location problem
• bin packing
• ...

Answer 1

In colloquial terms, Robust Optimization (RO) is a methodology (including modeling approach and computational methods) for handling optimization problems with uncertain data. Many times data aren't really measured exactly, and even more, in some contexts these measurement errors can trigger infeasibility on the optimization models (a quite undesirable behavior...). A common reference is Robust Optimization by A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, a free version can be found online in Nemirovski's website.

In RO, data are known to belong to an uncertainty set. That's a different modelling approach to Stochastic Programming, where data come from a specific probability distribution. Here, the objective and constraint functions are assumed to belong to these uncertainty sets. The goal is to make a decision that is feasible no matter what the constraints turn out to be, and optimal for the worst-case objective function.

Adapting formal definitions and notation from a publication by Ben-Tal and Nemirovski:

Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization–methodology and applications. Mathematical programming, 92(3), 453-480.

A generic mathematical programming problem is of the form: \begin{equation} \begin{array}{rrclcl} \displaystyle \min_{x_0 \in \mathbb{R}, x \in \mathbb{R}^n} & {x_0} \\ \textrm{s.t.} & f_0(x,\zeta) & \leq & x_0 \\ & f_i(x,\zeta) & \leq & 0 & & i = 1, \ldots, m \\ \end{array} \end{equation} where $x$ in the design vector, the functions $f_0$ (objective function) and $f_1,\ldots,f_m$ are structural elements of the problem, and $\zeta$ stands for the data specifying a particular problem instance. This notation is quite general, as the functions could be linear or nonlinear.

To take uncertainty into account a robust counterpart is associated to the previous problem, introducing an uncertainty set $\mathcal{U}$ of all possible values for $\zeta$. That is, there are several (could be an infinite set) possible scenarios. The robust counterpart is:

\begin{equation} \begin{array}{rrclcll} \displaystyle \min_{x_0 \in \mathbb{R}, x \in \mathbb{R}^n} & {x_0} \\ \textrm{s.t.} & f_0(x,\zeta) & \leq & x_0 & \forall \zeta \in \mathcal{U} \\ & f_i(x,\zeta) & \leq & 0 & i = 1, \ldots, m, \; \forall \zeta \in \mathcal{U} \\ \end{array} \end{equation}

Citing from the source:

For real-world optimization problems, the "decision environment" is often characterized by the following facts:

1. The data are uncertain/inexact
2. The optimal solution, even if computed very accurately, may be difficult to implement accurately
3. The constraints must remain feasible for all the meaningful realizations of the data
4. Problems are large-scale ($n$ or/and $m$ are large)
5. "Bad" optimal solutions (those which become severely infeasible in the face of even relatively small changes in the nominal data) are not uncommon.

Facts 1. and 2. motivate the uncertainty set $\mathcal{U}$ for the data, while 3. relates to including $\forall \zeta \in \mathcal{U}$ into the constraints.

So, the question is in which cases the latter optimization problem can be formulated as (or approximated by) a computationally tractable problem. The reference then goes on to study robust optimization for linear, conic quadratic and semidefinite programs.

---

With regards to the second part of the question I remember the following one for routing, where they study a VRPTW with uncertain service times and solve realistic instances via branch and price:

Souyris, S., Cortés, C. E., Ordóñez, F., & Weintraub, A. (2013). A robust optimization approach to dispatching technicians under stochastic service times. Optimization Letters, 7(7), 1549-1568.

Other works consider uncertainty in demand and/or travel times. I'm not familiar with approaches for shift rostering, facility location or bin packing so I'd rather not speak of them (even though a Google Scholar search yields some cases), probably other people can lend a helpful hand on that.