Using the idea of expanded core for the exact solution of bi‐objective multi‐dimensional knapsack problems

Using the idea of expanded core for the exact solution of bi‐objective multi‐dimensional knapsack problems

0.00 Avg rating0 Votes
Article ID: iaor20113695
Volume: 49
Issue: 4
Start Page Number: 589
End Page Number: 606
Publication Date: Apr 2011
Journal: Journal of Global Optimization
Authors: , ,
Keywords: programming: multiple criteria, programming: branch and bound, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.