Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
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 -