Solving the bi-objective multidimensional knapsack problem exploiting the concept of core

George Mavrotas, José Rui Figueira and Kostas Florios ()

MPRA Paper from University Library of Munich, Germany

Abstract: This paper discusses the bi-objective multi-dimensional knapsack problem. We propose the refinement of the core concept that has already effectively been used in the single objective multi-dimensional knapsack. The core concept is based on the divide and conquer principle. Instead of solving the whole problem with n variables, several sub-problems with less than n variables are solved, in several variables which comprise the cores. The quality of the obtained solution can be adjusted according to the core size and there is always a balance between the solution time and quality. First, the core variables are defined, and subsequently the bi-objective integer program is solved, that comprises only the core variables using the Multicriteria Branch and Bound algorithm that generates the complete Pareto set. Small and medium sized examples are solved. Also, a very small example is used to illustrate the method while computational issues are also discussed.

Keywords: Combinatorial optimization; Branch-and-bound; Multi-objective programming; Multi-dimensional knapsack problems (search for similar items in EconPapers)
JEL-codes: C61 C63 (search for similar items in EconPapers)
Date: 2009-12-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Published in Applied Mathematics and Computation 7.215(2009): pp. 2502-2514

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/105087/1/MPRA_paper_105087.pdf original version (application/pdf)

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:pra:mprapa:105087

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().