A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem

• We develop a new lower bound for minmax regret combinatorial optimization problems.
• We give algorithms that improve the approximation guarantee of the midpoint solution.
• We use the new lower bound to improve exact branch and bound algorithms.

Minmax regret optimization aims at finding robust solutions that perform best in the worst-case, compared to the respective optimum objective value in each scenario. Even for simple uncertainty sets like boxes, most polynomially solvable optimization problems have strongly NP-complete minmax regret counterparts. Thus, heuristics with performance guarantees can potentially be of great value, but only few such guarantees exist.A popular heuristic for combinatorial optimization problems is to compute the midpoint solution of the original problem. It is a well-known result that the regret of the midpoint solution is at most 2 times the optimal regret. Besides some academic instances showing that this bound is tight, most instances reveal a way better approximation ratio.We introduce a new lower bound for the optimal value of the minmax regret problem. Using this lower bound we state an algorithm that gives an instance-dependent performance guarantee for the midpoint solution that is at most 2. The computational complexity of the algorithm depends on the minmax regret problem under consideration; we show that our sharpened guarantee can be computed in strongly polynomial time for several classes of combinatorial optimization problems.To illustrate the quality of the proposed bound, we use it within a branch and bound framework for the robust shortest path problem. In an experimental study comparing this approach with a bound from the literature, we find a considerable improvement in computation times.