Optimization Online


Piecewise constant decision rules via branch-and-bound based scenario detection for integer adjustable robust optimization

Ward Romeijnders (w.romeijnders***at***rug.nl)
Krzysztof Postek (postek***at***ese.eur.nl)

Abstract: Multi-stage 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. Postek and den Hertog (2016) and Bertsimas and Dunning (2016) propose to solve these problems by constructing piecewise constant decision rules by adaptively partitioning the uncertainty set. The partitions of this set are iteratively updated by separating so-called critical scenarios of the uncertain parameters. Both references present methods for identifying these critical scenarios. However, these methods are most suitable for problems with continuous decision variables and many uncertain constraints. In particular, they are not able to identify informative sets of critical scenarios for integer problems with uncertainty in the objective function only. In this note, we address this shortcoming of existing methods by introducing a general critical scenario detection method for mixed-integer adjustable robust optimization problems that is based on 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 the problem-specific approach of Postek and den Hertog (2016).

Keywords: robust optimization; adjustability; adaptivity; mixed-integer

Category 1: Robust Optimization

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 05/24/2018
Entry Accepted: 05/24/2018
Entry Last Modified: 11/14/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society