The robust multiple-choice multidimensional knapsack problem

Marco Caserta and Stefan Voß

Omega, 2019, vol. 86, issue C, 16-27

Abstract: 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.

Keywords: Robust optimization; Knapsack problems; Mixed-integer programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048317305777
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:86:y:2019:i:c:p:16-27

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2018.06.014

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().