Optimal Information Discovery in Correlated Environments: Measuring the Value of Information

We study linear combinatorial optimization problems where uncertain disruptions may affect the components (i.e., coefficients) of the objective function. To mitigate the impact of these disruptions, a planner can allocate a limited probing budget to fully reveal the status of selected components, while unprobed components status must be estimated. In contrast to settings assuming independence, we consider correlated disruptions, where the probability distribution of unprobed components depends on the information revealed through probing. Under this partial information, the planner then solves the optimization problem and implements the resulting solution. Afterward, the remaining uncertainty is revealed and the actual reward is realized. The planner’s goal is to select a probing plan that maximizes the value of information, namely, the expected actual reward. We show that the best way to estimate the value of unprobed components is by using the conditional expected value. We then reformulate the probing problem as a decision-dependent stochastic mixed-integer bilevel optimization problem with multiple followers and propose two formulations based on the value function reformulation. The first one represents conditional probabilities as a maximum flow problem over an auxiliary graph, and the second one uses the concept of consistency sets where the decision-dependent probability constraints are modeled with auxiliary binary variables. Both reformulations are solved via a customized branch-and-cut algorithm. We present a computational study on small-to-medium size instances of two problems: the longest path problem (central to project management) and the 0-1 knapsack problem (central to project selection). We provide insights regarding which of the formulations is preferred given the structure of the uncertainty set. We demonstrate that little information goes a long way: probing a small fraction of components can lead to considerable gains in the solution quality. Moreover, we demonstrate that accounting for correlations is worthwhile, as it yields substantial improvements in solution quality.

Article

Download

View PDF