Dear all,



I would like to solve a problem similar to a multiple knapsack problem and
am looking for a function in R that can help me.



Specifically, my situation is as follows: I have a list of n items which I
would like to allocate to m groups with fixed size. Each item has a certain
profit value and this profit depends on the type of group the item is in. My
problem is to allocate the items into groups so the overall profit is
maximized while respecting the fixed size of each group.



Take the following example with 20 items (n=5) and 5 groups (m=5):

set.seed(1)

profits <- matrix(runif(100), nrow=20)

size<-c(2,3,4,5,6)



The matrix "profits" describes the profit of each item when it is allocated
to a certain group. For example, when item 1 is allocated to group 1 it
generates a profit of 0.26550866. However, when item 1 is allocated to group
2 it generates a profit of 0.93470523. The matrix "size" describes the size
of each group. So group 1 can contain 2 items, group 2 3 items, group 4 4
items, etc.



I think this is probably something that could be done with constrOptim() but
I'm not exactly sure how.



Any help is very much appreciated!



Thanks very much in advance,



Michael







Michael Haenlein

Associate Professor of Marketing

ESCP Europe

Paris, France

	[[alternative HTML version deleted]]

