Robust Optimization with Decision-Dependent Information Discovery

• 成果类型: Article; Early Access
• 署名作者: Vayanos, Phebe; Georghiou, Angelos; Yu, Han
• 署名单位: University of Southern California; University of Southern California; University of Southern California; University of Cyprus
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2021.00160
• 发表日期: 2025
• 关键词: Robust Optimization; Endogenous uncertainty; decision-dependent information discovery; Pandora box problem; R&D project portfolio selection; Preference elicitation; kidney allocation

摘要

Robust optimization (RO) is a popular paradigm for modeling and solving twoand multistage decision-making problems affected by uncertainty. In many real-world applications, such as R&D project selection, production planning, or preference elicitation for product or policy recommendations, the time of information discovery is decision-dependent and the uncertain parameters only become observable after an often costly investment. Yet, most of the literature on robust optimization assumes 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. To fill this gap in the practicability of RO, we consider two- and multistage robust optimization problems in which part of the decision variables control the time of information discovery. Thus, information available at any given time is decisiondependent 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 Kadaptability 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 finite mixed-integer (resp. bilinear) program if none (resp. some) of the decision variables are real-valued. This finite program is solvable with off-the-shelf solvers. We generalize our approach to the minimization of piecewise linear convex functions. We demonstrate the effectiveness of our method in terms of usability, optimality, and speed on synthetic instances of the Pandora box problem, the preference elicitation problem with realvalued recommendations, the best box problem, and the R&D project portfolio optimization problem. Finally, we evaluate it on an instance of the active preference elicitation problem used to recommend kidney allocation policies to policy-makers at the United Network for Organ Sharing based on real data from the U.S. Kidney Allocation System.