optimization: multiple assignment problem
It would be more clear if you tell, what you want to do instead of what you do not want to do. If you start with a usual cost matrix (whatever cost function you have) and you have to assign N to N this reduces to the well-known Munkre?s algorithm (see for example: http://gallery.rcpp.org/articles/minimal-assignment/). If you have to assign M to N, it is an extended version of the Munkre?s algorithm which has been covered by Bourgeois and Lassalle (1971). All this is graph theory. Best Simon
On 14 Nov 2013, at 19:24, Jean-Francois Chevalier <Jean-Francois.Chevalier at bisnode.com> wrote:
Hello,
I'm trying to solve a multiple assignment problem.
I found a package Adagio and its function mknapsack which
maximize vstar = p(1)*(x(1,1) + ... + x(m,1)) + ... ... + p(n)*(x(1,n) + ... + x(m,n))
subject to w(1)*x(i,1) + ... + w(n)*x(i,n) <= k(i) for i=1,...,m
x(1,j) + ... + x(m,j) <= 1 for j=1,...,n x(i,j) = 0 or 1 for i=1,...,m , j=1,...,n ,
It's close to what I'm trying to do except that
1)k(i) = k for any I (not an issue)
2)p is dependent of the item AND the knapsack
3)each item must be assigned
maximize vstar = p(1,1)*x(1,1) + ... + p(m,1)*x(m,1) + ... ... + p(1,n)*x(1,n) + ... + p(m,n)*x(m,n)
with p(j,i) profit of assigning item i to knapsack j
subject to w(1)*x(i,1) + ... + w(n)*x(i,n) <= k for i=1,...,m
x(1,j) + ... + x(m,j) = 1 for j=1,...,n x(i,j) = 0 or 1 for i=1,...,m , j=1,...,n ,
It would be really helpful if you could indicate me any package, function that would solve my problem?
Thanks in advance,
Best regards,
Jean-Fran?ois
**** DISCLAIMER ****\ "This e-mail and any attachments t...{{dropped:13}}
______________________________________________ R-help at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.