École Nationale Supérieure de
Techniques Avancées

Résumé

In this project, we investigate a class of two-stage stochastic problems. The first stage involves selecting which information to query, while the second stage focuses on solving a specific binary problem based on the revealed information. The linking constraints in our model function as information discovery constraints, adding complexity to the decision-making process. To effectively tackle the uncertainty inherent in these problems, we develop a decomposition method that separates the problem into more manageable components. Additionally, we propose a deterministic equivalent formulation by convexifying the recourse feasible region. Our analysis shows that, for the cases we consider, this relaxation is exact. Given the exponential number of integer solutions that arise after convexification, we employ column generation to efficiently solve the problem. Furthermore, we apply our methodology to two distinct applications: the knapsack problem and the kidney exchange problem. Finally, we conduct a comparative analysis between our approach and the extensive MIP formulation, with the aim of identifying its limitations and potential avenues for future improvement.