optimization: multiple assignment problem

An embedded and charset-unspecified text was scrubbed...
Name: not available
URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20131114/e7a50191/attachment.pl>
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

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.
Jean-Francois Chevalier <Jean-Francois.Chevalier <at> bisnode.com> writes:

You have already given the answer yourself. You have binary variables x(j, i),
you need to set up the inequalities, and then apply one of the mixed-integer
linear programming solvers in R, for instance 'lpSolve', 'Rglpk', 'Rsymphony'.

Setting up the inequalities may be slightly involved. You have not provided
reproducible code, so no concrete answer possible.

Hans Werner
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