An exact algorithm for the knapsack sharing problem with common items

An exact algorithm for the knapsack sharing problem with common items

0.00 Avg rating0 Votes
Article ID: iaor2007884
Country: Netherlands
Volume: 171
Issue: 2
Start Page Number: 693
End Page Number: 707
Publication Date: Jun 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization, combinatorial optimization
Abstract:

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, Nk (k = 0, 1, … , s). The player k is concerned only with the items in N0 ∪ Nk, where N0 is the set of ‘common’ items, while Nk represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.

Reviews

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