Oracle-based algorithms for binary two-stage robust optimization
- PDF / 1,950,538 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 190 Views
Oracle‑based algorithms for binary two‑stage robust optimization Nicolas Kämmerling1 · Jannis Kurtz2 Received: 20 May 2019 © The Author(s) 2020
Abstract In this work we study binary two-stage robust optimization problems with objective uncertainty. We present an algorithm to calculate efficiently lower bounds for the binary two-stage robust problem by solving alternately the underlying deterministic problem and an adversarial problem. For the deterministic problem any oracle can be used which returns an optimal solution for every possible scenario. We show that the latter lower bound can be implemented in a branch and bound procedure, where the branching is performed only over the first-stage decision variables. All results even hold for non-linear objective functions which are concave in the uncertain parameters. As an alternative solution method we apply a column-and-constraint generation algorithm to the binary two-stage robust problem with objective uncertainty. We test both algorithms on benchmark instances of the uncapacitated singleallocation hub-location problem and of the capital budgeting problem. Our results show that the branch and bound procedure outperforms the column-and-constraint generation algorithm. Keywords Two-stage robust optimization · Non-linear binary optimization · Branch and bound algorithm
* Jannis Kurtz [email protected]‑aachen.de Nicolas Kämmerling [email protected]‑dortmund.de 1
Institute of Transport Logistics, TU Dortmund University, Leonhard‑Euler‑Straße 2, 44227 Dortmund, Germany
2
Chair for Mathematics of Information Processing, RWTH Aachen University, Pontdriesch 12‑14, 52062 Aachen, Germany
13
Vol.:(0123456789)
N. Kämmerling, J. Kurtz
1 Introduction The concept of robust optimization was created to tackle optimization problems with uncertain parameters. The basic idea behind this concept is to use uncertainty sets instead of probability distributions to model uncertainty. More precisely it is assumed that all realizations of the uncertain parameters, called scenarios, are contained in a known uncertainty set. Instead of optimizing the expected objective value or a given risk-measure as common in the field of stochastic optimization, in the robust optimization framework we calculate solutions which are optimal in the worst case and which are feasible for all scenarios in the uncertainty set. The concept was first introduced in [67]. Later it was studied for combinatorial optimization problems with discrete uncertainty sets in [53], for conic and ellipsoidal uncertainty in [13, 14], for semi-definite and least-square problems in [39, 40] and for budgeted uncertainty in [26, 27]. An overview of the robust optimization literature can be found in [2, 10, 15, 32]. The so called robust counterpart is known to be NP-hard for most of the classical combinatorial problems, although most of them can be solved in polynomial time in its deterministic version; see [53]. Furthermore it is a well-known drawback of this approach that the optimal solutions are often too conservat
Data Loading...
