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.