Advertisement
Published in:
2006 | OriginalPaper | Chapter
MVRC Heuristic for Solving the Multi-Choice Multi-Constraint Knapsack Problem
Authors : Maria Chantzara, Miltiades Anagnostou
Published in: Computational Science – ICCS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper presents the heuristic algorithm Maximizing Value per Resources Consumption (MVRC) that solves the Multi-Choice Multi-Constraint Knapsack Problem, a variant of the known NP-hard optimization problem called Knapsack problem. Starting with an initial solution, the MVRC performs iterative improvements through exchanging the already picked items in order to conclude to the optimal solution. Following a three step procedure, it tries to pick the items with the maximum Value per Aggregate Resources Consumption. The proposed algorithm has been evaluated in terms of the quality of the final solution and its run-time performance.