Robust efficiency measures for linear knapsack problem variants

Christopher Wishon and J. Rene Villalobos

European Journal of Operational Research, 2016, vol. 254, issue 2, 398-409

Abstract: Numerous combinatorial optimization applications, such as the mobile retailer product mix problem, utilize the multidemand, multidimensional knapsack problem variant in which there are multiple knapsack constraints requiring a weighted summation of the variables to be less than or equal to a nonnegative value and multiple demand constraints requiring a weighted summation of the variables to be greater than or equal to a nonnegative value. The purpose of this paper is to demonstrate that core variables and efficiency measures, concepts used in the most efficient solvers to-date for binary knapsack problems and some of its variants, can be extended to the multidemand, multidimensional knapsack problem variant. Specifically, new efficiency measure calculations are provided and their properties are mathematically proven and experimentally demonstrated. The contribution of such measures to knapsack problem research is that these measures are applicable to all knapsack problem variants with a single linear objective function and linear constraints of any quantity. The applicability of these new measures is demonstrated through the development of three heuristic procedures: a Fixed-Core heuristic, a Genetic Algorithm, and a Kernel Search heuristic. The results from these tests are compared with the results from a commercial solver and an existing heuristic. The findings from these tests demonstrate that the Fixed-Core and Kernel Search heuristics developed for this paper are the most efficient solvers to-date for hard multidemand, multidimensional knapsack problems.

Keywords: Combinatorial optimization; Heuristic; Genetic Algorithm; Knapsack problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716302442
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:ejores:v:254:y:2016:i:2:p:398-409

DOI: 10.1016/j.ejor.2016.04.025

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().