Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique
Xiaoyu Chen
( LIRMM-Montpellier )Salle 2, IMB
November 12, 2026 at 11:00 AM
We consider a four-stage variant of robust optimization with cost uncertainty described by the budget uncertainty polytope, known as decision-dependent information discovery (DDID), in which the decision maker first queries a subset of the cost coefficients. The adversary responds by revealing worst-case values for the queried elements, after which the decision maker chooses a feasible solution while facing the remaining uncertainty on the unqueried costs. Our contribution is twofold. On the negative side, we prove that the problem is NP-complete even when the underlying nominal problem is the 2-selection problem, for which only a polynomial number of feasible solutions exist. On the positive side, we prove that the more general p-selection problem can be solved in polynomial time under the additional assumption that all deviations are equal.