R help - Nov 2013 - optimization: multiple assignment problem

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}}

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.

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