A GRASP algorithm for the multi-objective knapsack problem

Dalessandro Vianna (dalessandroucam-campos.br)
José Elias Arroyo (jclaudioucam-campos.br)

Abstract: In this article, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, each one with r costs and r weights, have to be inserted in r knapsacks with different capacities in order to maximize the r total costs (objectives). The algorithm is based on a weighted scalar function (linear combination of the objectives), for it is necessary to define a preference or weight for each objective. At each iteration of the algorithm, a preference vector is defined and a solution is built considering the preferences of each objective. The found solution is submitted to a local search trying to improve its weighted scalar function. In order to find a variety of efficient solutions, we use different preference vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r = 2, 3, 4 objectives and n = 250, 500, 750 items. The quality of the approximated solutions is evaluated comparing with the solutions given by two genetic algorithms from the literature.

Keywords: algorithm, multi-objective combinatorial optimization, knapsack problem.

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: Accepted for the XXIV SCCC

Download: [Compressed Postscript]

Entry Submitted: 08/30/2004
Entry Accepted: 08/31/2004
Entry Last Modified: 08/30/2004

Modify/Update this entry