Munich Personal RePEc Archive

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

Mavrotas, George and Figueira, José Rui and Florios, Kostas (2009): Solving the bi-objective multidimensional knapsack problem exploiting the concept of core. Published in: Applied Mathematics and Computation , Vol. 215, No. 7 (1 December 2009): pp. 2502-2514.

[img]
Preview
PDF
MPRA_paper_105087.pdf

Download (487kB) | Preview

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.

UB_LMU-Logo
MPRA is a RePEc service hosted by
the Munich University Library in Germany.