# [R] optimization: multiple assignment problem

Simon Zehnder szehnder at uni-bonn.de
Thu Nov 14 19:50:23 CET 2013

```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?
> 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