Optimization Online


A GRASP algorithm for the multi-objective knapsack problem

Dalessandro Vianna (dalessandro***at***ucam-campos.br)
Josť Elias Arroyo (jclaudio***at***ucam-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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society