TY - JOUR

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

AU - Chassein, André B.

AU - Goerigk, Marc

PY - 2015/8/1

Y1 - 2015/8/1

N2 - Abstract 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.

AB - Abstract 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.

KW - Approximation

KW - Combinatorial optimization

KW - Minmax regret

KW - Robust optimization

KW - Robust shortest paths

U2 - 10.1016/j.ejor.2015.02.023

DO - 10.1016/j.ejor.2015.02.023

M3 - Journal article

AN - SCOPUS:84926422188

VL - 244

SP - 739

EP - 747

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

M1 - 12792

ER -