The robust multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) assumes n sets composed of mutually exclusive items. The goal is to select exactly one item per set, maximizing the overall utility, without violating a family of knapsack constraints. Motivated by recent applications of the MMKP to complex system reliability and quality of service management problems, we propose a robust version. More specifically, we relinquish the assumption that the problem parameters are deterministically known by limiting their values to a pre-specified uncertainty set. Depending on the structure of the variance−covariance matrix used to model the uncertainty, we identify four different cases, leading to robust formulations characterized by second order cone programs. We show how each of these programs is transformed into an equivalent linear program, implying that the use of a robust formulation for the MMKP comes with no extra computational complexity. Finally, using a novel matheuristic designed for the MMKP, we shed lights on the trade-off between the “price of robustness,” i.e., how much worse the objective function value of a robust solution is, compared with the deterministic one, and the “reliability,” i.e., the probability that a robust solution will lead to a feasible scenario for an arbitrary realization of the uncertain parameters.