Ranking robustness

Quite recently, our new approach for robust optimisation in combination with K-best ranking problems has been published.

In robust optimisation, we’d like to find solutions which perform well over a range of possible scenario outcomes. For K-best problems, we are interested in finding not only a best possible solution for a (deterministic) problem, but also the second best, the third best, and so on.

So what do these two problems have to do with each other? One could certainly look at K-best problems under uncertainty, that is, finding second best solutions for robust problems, third best, and so on. I don’t think anyone has ever tried that!

Our idea was instead to use such ranking algorithms to determine what a “good solution” means under uncertainty. The classic approach to determine the quality of a solution would be to calculate the worst objective value over all scenarios. In our approach, we calculate the worst ranking over all scenarios instead.

This idea was inspired by many real-world problems, where the specific objective value of a solution is only one of many indicators what a “good” solution constitutes. Under many circumstances, a more natural approach for a decision maker is to give a rough quality estimate, say in terms of “good”, “ok”, “bad”, or “very bad”, for example. We try to find a solution for which the worst such ranking over all scenarios is as high as possible.

K-best problems are tough to solve on their own, and it doesn’t get easier if you include that as a subproblem for robust optimisation. Accordingly, a big future challenge for us will be to produce high-quality ranking robust solutions in shorter computation time.

This is the abstract:

We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.

We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.