Optimization Online


Robust Optimization with Decision-Dependent Information Discovery

Phebe Vayanos (phebe.vayanos***at***usc.edu)
Angelos Georghiou (angelos.georghiou***at***mcgill.ca)
Han Yu (hyu376***at***usc.edu)

Abstract: Robust optimization is a popular paradigm for modeling and solving two- and multi-stage decision-making problems affected by uncertainty. Most approaches assume that the uncertain parameters can be observed for free and that the sequence in which they are revealed is independent of the decision-maker's actions. Yet, these assumptions fail to hold in many real-world applications where the time of information discovery is decision-dependent and the uncertain parameters only become observable after an often costly investment. To fill this gap, we consider two- and multi-stage robust optimization problems in which part of the decision variables control the time of information discovery. Thus, information available at any given time is decision-dependent and can be discovered (at least in part) by making strategic exploratory investments in previous stages. We propose a novel dynamic formulation of the problem and prove its correctness. We leverage our model to provide a solution method inspired from the K-adaptability approximation, whereby K candidate strategies for each decision stage are chosen here-and-now and, at the beginning of each period, the best of these strategies is selected after the uncertain parameters that were chosen to be observed are revealed. We reformulate the problem as a mixed-binary linear program solvable with off-the-shelf solvers. We generalize our approach to the minimization of piecewise linear convex functions. We demonstrate effectiveness of our approach on synthetic and real data instances of the active preference elicitation problem used to recommend policies that meet the needs of policy-makers at the Los Angeles Homeless Services Authority.

Keywords: robust optimization, endogenous uncertainty, decision-dependent information discovery, integer programming

Category 1: Robust Optimization

Citation: Technical Report, University of Southern California, September 2019

Download: [PDF]

Entry Submitted: 09/18/2019
Entry Accepted: 09/18/2019
Entry Last Modified: 01/16/2021

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