In this talk we present an information discovery framework in optimization under uncertainty. In this framework, uncertain parameters are assumed to be “discoverable” by the decision-maker under a given discovery (query) budget. The decision-maker therefore decides which parameters to discover (query) in a first stage then solves an optimization problem with the discovered uncertain parameters at hand in a second stage. We model this problem as a two-stage stochastic program and develop decomposition algorithms for its solution. Notably, one of the algorithms we propose reposes on a Dantzig-Wolfe reformulation of the recourse problem. This allows to treat the cases where the recourse problem involves binary decisions without relying on integer L-Shaped cuts. In its implementation, this approach requires to couple Benders’ and Dantzig-Wolfe reformulation with the subproblems of the Benders’ algorithm being solved using the column generation algorithm. We present some preliminary results on the kidney exchange problem under uncertainty of the compatibility information.