Exact and Approximate Schemes for Robust Optimization Problems with Decision-Dependent Information Discovery

Uncertain optimization problems with decision-dependent information discovery allow the decision maker to control the timing of information discovery, in contrast to the classic multistage setting where uncertain parameters are revealed sequentially based on a prescribed filtration. This problem class is useful in a wide range of applications; however, its assimilation is partly limited by the lack of efficient solution schemes. In this paper, we study two-stage robust optimization problems with decision-dependent information discovery where uncertainty appears in the objective function. The contributions of the paper are twofold: (i) we develop the first exact algorithm for this class of problems, and (ii) we improve upon the existing K-adaptability approximation by strengthening its formulation using techniques from the integer programming literature. We benchmark our approaches using the decision-dependent information discovery orienteering and shortest path problems. We demonstrate that the exact solution method outperforms at times the K-adaptability approximation; however, the strengthened K-adaptability formulation can provide good-quality solutions in larger instances while significantly outperforming existing approximation schemes even in the decision-independent information discovery setting. We leverage the effectiveness of the proposed solution schemes and the orienteering problem in a case study from Alrijne Hospital in the Netherlands, where we try to improve the collection process of empty medicine delivery crates by cooptimizing sensor placement and routing decisions. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The authors gratefully acknowledge the financial support by the Dutch Institute of Advanced Logistics (Dinalog) [grant number 2017-2-131TKI]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0290 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0290 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .