Recoverable Robustness in Combinatorial Optimization

Combinatorial optimization is an important tool for solving optimization problems from industry like vehicle routing, network design or production scheduling. To define such an optimization problem, data concerning the cost, the constraints on the solutions or the topology of the networks ar assumed to be known. However, these data can often only be estimated based on imprecise measuring methods or predictions of future events (development of the stock markets. change of weather conditions, variations in traffic volume). In several applications, average values from historical data adjusted by some anticipated changes are used to determine the problem setting.

An attractive approach for dealing with these variations in data is to include different data sets into the optimization process. Many researchers have selected a scenario approach, where each scenario represents a reasonable data set. Depending on the considered setting and the available information, such a set of data sets is equipped with a probability distribution to reflect the likelihoods of the scenarios.