Piecewise Constant Decision Rules via Branch-and-Bound Based Scenario Detection for Integer Adjustable Robust Optimization

Ward Romeijnders () and Krzysztof Postek ()
Additional contact information
Ward Romeijnders: Department of Operations, Faculty of Economics and Business, University of Groningen, 9700 AV Groningen, Netherlands
Krzysztof Postek: Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 390-400

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

Keywords: robust optimization; adjustability; adaptivity; mixed-integer (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0934 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:390-400

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().