Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

Kostas Florios (), George Mavrotas and Danae Diakoulaki

European Journal of Operational Research, 2010, vol. 203, issue 1, 14-21

Abstract: In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive [epsilon]-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932-942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive [epsilon] -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).

Keywords: Branch; and; bound; Knapsack; problem; Multiobjective; Evolutionary; algorithms (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00497-4
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:203:y:2010:i:1:p:14-21

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 ().