.png){kind=icon}
.png){kind=icon}
Return
The robust multiple-choice multidimensional knapsack problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.omega.2018.06.014.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2018 Elsevier Ltd. All rights reserved.
Keywords:
Robust optimization
Knapsack problems
Mixed-integer programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
O
IF:
7.2
Papers:
3.7K
Citations:
1.4W
