Orateur
Description
We consider a two-stage stochastic decision problem where the decision-maker has the opportunity to obtain information about the distribution of the random variables X through a set of discrete actions that we refer to as probing. Specifically, probing allows the decision-maker to observe components of a random vector Y that is jointly-distributed with X. We propose a three-stage optimization model for this problem, wherein the first-stage variables select components of Y to observe, and decisions in subsequent stages must be consistent with the obtained information. In the case that X and Y have finite support, Goel and Grossmann gave a mixed-integer programming formulation of this problem whose size is proportional to the square of cardinality of the sample space of the random variables. We propose to solve the model using bounds obtained from an information-based relaxation, combined with a branching scheme that enforces the consistency of decisions with observed information. The branch-and-bound approach can naturally be combined with sampling in order to estimate both lower and upper bounds on the optimal solution value. We demonstrate the scalability of our approach against the exact MIP formulation on instances of a stochastic facility location problem.
