Robust Combinatorial Optimization and Simulation

Robust Combinatorial Optimization and Simulation

Real-life planning problems are often complicated by the occurrence of disturbances, which imply that the original plan cannot be followed anymore and some recovery action must be taken to cope with the disturbance. In such a situation it is worthwhile to arm yourself against possible disturbances. An important area of research is robustness: we look for solutions that either remain valid in case of a disturbance, or can easily be adjusted to a feasible solution without having to solve the problem all over again. Possible approaches in this respect are:

  • Take robustness as the objective function
  • Work with probability distributions and chance constraints.
  • Apply the concept of recoverable robustness. Recoverable robust optimization computes solutions, which for a given set of scenarios can be recovered to a feasible solution according to a set of pre-described, fast, and simple recovery algorithms.
  • Combined simulation and optimization. Within our optimization algorithms (e.g. local search)we use simulation to assess the quality of solutions including the effect of disturbances, which outcome we use to guide us to an optimal solution.

Finally, to test whether our algorithm gives the desired result in case of real-life disturbances, we apply discrete event simulation afterwards, if possible. We investigate well-known combinatorial optimization problems such as knapsack and shortest path, as well as applications e.g. in airport operations and vehicle routing.