

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,
JeanFrançois
**** DISCLAIMER ****\ "This email and any attachments t...{{dropped:13}}
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


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 wellknown Munkre’s algorithm (see for example: http://gallery.rcpp.org/articles/minimalassignment/). 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, JeanFrancois Chevalier < [hidden email]> 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,
>
> JeanFrançois
>
>
>
> **** DISCLAIMER ****\ "This email and any attachments t...{{dropped:13}}
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/rhelp> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html> and provide commented, minimal, selfcontained, reproducible code.
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


In reply to this post by JeanFrancois Chevalier
JeanFrancois Chevalier <JeanFrancois.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 mixedinteger
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,
> JeanFrançois
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.

