Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems |
| |
Authors: | George Mavrotas José Rui Figueira Alexandros Antoniadis |
| |
Affiliation: | (1) LGI2P, Parc Scientifique Georges Besse, 30035 Nimes, Cedex 1, France |
| |
Abstract: | We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting
the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems
and it 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). In the multi-objective case, the
general idea is that we start from an approximation of the Pareto set (produced with the Multi-Criteria Branch and Bound algorithm,
using also the core concept) and we enrich this approximation iteratively. Every time an approximation is generated, we solve
a series of appropriate single objective Integer Programming (IP) problems exploring the criterion space for possibly undiscovered,
new Pareto Optimal Solutions (POS). If one or more new POS are found, we appropriately expand the already found cores and
solve the new core problems. This process is repeated until no new POS are found from the IP problems. The paper includes
an educational example and some experiments. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|