ROADEF 2026>
Decision-dependent information discovery for robust cardinality-constrained combinatorial optimization problems
Xiaoyu Chen  1@  , Michael Poss  2@  
1 : LIRMM, University of Montpellier, CNRS
CNRS
2 : LIRMM, University of Montpellier, CNRS
CNRS

Given a combinatorial optimization problem $\Pi$, its generalized cardinality-constrained counterpart GenCard-$\Pi$ limits the number of non-zero elements in some given set by some given integer. We study a setting where the unit weights in this cardinality constraint are uncertain, but can be partially queried before solving the problem, and may take fractional values when revealed. Overall, DDID-$\Pi$ is a three-stage problem with a robust constraint: (i) we select a subset of items whose weights will be queried, (ii) an adversary reveals the values of these queried weights, and (iii) we compute the cheapest feasible solution, robust against variations in the unqueried weights. We first show that DDID-$\Pi$ is NP-hard in general. Then, when the number of queries is fixed, we provide an algorithm for DDID-$\Pi$ that solves a polynomial number of GenCard-$\Pi$ instances and of compact linear programs. We further observe that the solutions of GenCard-$\Pi$ instances can also be obtained from instances of $\Pi$ with a constant number of variables fixed to 1 when $\Pi$ involves an exact cardinality constraint.


Chargement... Chargement...