Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core

• Published in: Applied mathematics and computation 2009-12, Vol.215 (7), p.2502-2514
• Main Authors: Mavrotas, George, Figueira, José Rui, Florios, Kostas
• Format: Article
• Language: English
• Subjects: Core; Exact sciences and technology; Knapsack; Mathematical analysis; Mathematics; Multi-dimensional; Multi-objective programming; Numerical analysis; Numerical analysis. Scientific computation; Sciences and techniques of general use
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2009.08.045

This paper deals with the bi-objective multi-dimensional knapsack problem. We propose the adaptation of the core concept that is effectively used in single-objective multi-dimensional knapsack problems. The main idea of the core concept is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). The quality of the obtained solution can be adjusted according to the size of the core and there is always a trade off between the solution time and the quality of solution. In the specific study we define the core problem for the multi-objective multi-dimensional knapsack problem. After defining the core we solve the bi-objective integer programming that comprises only the core variables using the Multicriteria Branch and Bound algorithm that can generate the complete Pareto set in small and medium size multi-objective integer programming problems. A small example is used to illustrate the method while computational and economy issues are also discussed. Computational experiments are also presented using available or appropriately modified benchmarks in order to examine the quality of Pareto set approximation with respect to the solution time. Extensions to the general multi-objective case as well as to the computation of the exact solution are also mentioned.