Piecewise Constant Decision Rules via Branch-and-Bound Based Scenario Detection for Integer Adjustable Robust Optimization
| Autor: | Krzysztof Postek, Ward Romeijnders |
|---|---|
| Přispěvatelé: | Econometrics, Research programme OPERA |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization 021103 operations research Branch and bound 0211 other engineering and technologies General Engineering Robust optimization 02 engineering and technology Decision rule 020901 industrial engineering & automation Optimization and Control (math.OC) Piecewise FOS: Mathematics Constant (mathematics) Mathematics - Optimization and Control Integer (computer science) Mathematics |
| Zdroj: | INFORMS Journal on Computing. INFORMS Institute for Operations Research and the Management Sciences INFORMS Journal on Computing, 33(1), 390-400. INFORMS |
| ISSN: | 1091-9856 |
| DOI: | 10.1287/ijoc.2019.0934 |
| Popis: | Multistage problems with uncertain parameters and integer decisions variables are among the most difficult applications of robust optimization (RO). The challenge in these problems is to find optimal here-and-now decisions, taking into account that the wait-and-see decisions have to adapt to the revealed values of the uncertain parameters. An existing approach to solve these problems is to construct piecewise constant decision rules by adaptively partitioning the uncertainty set. The partitions of this set are iteratively updated by separating so-called criticial scenarios, and methods for identifying these critical scenarios are available. However, these methods are most suitable for problems with continuous decision variables and many uncertain constraints, providing no mathematically rigorous methodology for partitioning in case of integer decisions. In particular, they are not able to identify sets of critical scenarios for integer problems with uncertainty in the objective function only. In this paper, we address this shortcoming by introducing a general critical scenario detection method. The new method leverages the information embedded in the dual vectors of the LP relaxations at the nodes of the branch-and-bound tree used to solve the corresponding static problem. Numerical experiments on a route planning problem show that our general-purpose method outperforms a problem-specific approach from the literature. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|