optimization: multiple assignment problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

optimization: multiple assignment problem

Jean-Francois Chevalier
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}}


______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: optimization: multiple assignment problem

szehnder@uni-bonn.de
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 <[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,
>
> Jean-François
>
>
>
> **** DISCLAIMER ****\ "This e-mail and any attachments t...{{dropped:13}}
>
> ______________________________________________
> [hidden email] 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.

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: optimization: multiple assignment problem

Hans W Borchers
In reply to this post by Jean-Francois Chevalier
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

______________________________________________
[hidden email] 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.