Hi, I have this problem: K candidates apply for a job. There are R referees available to review their resumes and provide feedback. Suppose that we would like M referees to review each candidate (M < R). How would I assign candidates to referees (or, conversely, referees to candidates)? There are two important cases: (a) K > (R choose M) and (b) K < (R chooses M). Case (a) actually reduces to case (b), so we only have to consider case (b). Without any other constraints, the problem is quite easy to solve. Here is an example that shows this. require(gtools) set.seed(12345) K <- 10 # number of candidates R <- 7 # number of referees M <- 3 # overlap, number of referees reviewing each candidate allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE) assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ] assignment> assignment[,1] [,2] [,3] [1,] 3 4 5 [2,] 3 5 7 [3,] 5 6 7 [4,] 3 5 6 [5,] 1 6 7 [6,] 1 2 7 [7,] 1 4 5 [8,] 3 6 7 [9,] 2 4 5 [10,] 4 5 7>Here each row stands for a candidate and the column stands for the referees who review that candidate. Of course, there are some constraints that make the assignment challenging. We would like to have an even distribution of the number of candidates reviewed by each referee. For example, the above code produces an assignment where referee #2 gets only 2 candidates and referee #5 gets 7 candidates. We would like to avoid such uneven assignments.> table(assignment)assignment 1 2 3 4 5 6 7 3 2 4 4 7 4 6>Note that in this example there are 35 possible triplets of referees and 10 candidates. Therefore, a perfectly even assignment is not possible. I tried some obvious, greedy search methods but they are not guaranteed to work. Any hints or suggestions would be greatly appreciated. Best, Ravi [[alternative HTML version deleted]]
> -----Original Message----- > From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] > On Behalf Of Ravi Varadhan > Sent: Wednesday, April 30, 2014 10:49 AM > To: r-help at r-project.org > Subject: [R] A combinatorial assignment problem > > Hi, > > I have this problem: K candidates apply for a job. There are R referees > available to review their resumes and provide feedback. Suppose that we > would like M referees to review each candidate (M < R). How would I > assign candidates to referees (or, conversely, referees to candidates)? > There are two important cases: (a) K > (R choose M) and (b) K < (R > chooses M). > > Case (a) actually reduces to case (b), so we only have to consider case > (b). Without any other constraints, the problem is quite easy to solve. > Here is an example that shows this. > > require(gtools) > set.seed(12345) > K <- 10 # number of candidates > R <- 7 # number of referees > M <- 3 # overlap, number of referees reviewing each candidate > > allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE) > assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ] > assignment > > assignment > [,1] [,2] [,3] > [1,] 3 4 5 > [2,] 3 5 7 > [3,] 5 6 7 > [4,] 3 5 6 > [5,] 1 6 7 > [6,] 1 2 7 > [7,] 1 4 5 > [8,] 3 6 7 > [9,] 2 4 5 > [10,] 4 5 7 > > > > Here each row stands for a candidate and the column stands for the > referees who review that candidate. > > Of course, there are some constraints that make the assignment > challenging. We would like to have an even distribution of the number of > candidates reviewed by each referee. For example, the above code produces > an assignment where referee #2 gets only 2 candidates and referee #5 gets > 7 candidates. We would like to avoid such uneven assignments. > > > table(assignment) > assignment > 1 2 3 4 5 6 7 > 3 2 4 4 7 4 6 > > > > Note that in this example there are 35 possible triplets of referees and > 10 candidates. Therefore, a perfectly even assignment is not possible. > > I tried some obvious, greedy search methods but they are not guaranteed to > work. Any hints or suggestions would be greatly appreciated. > > Best, > Ravi >Well, if you don't need clever, a brute force approach could work (depending on the values of k, r, and m). Something like this assignment <- function(k,r,m,max_iter=120) { n <- 0 cmb <- combn(r,m) repeat { n <- n+1 tbl <- table(map<-cmb[,sample(1:choose(r,m),k)]) if(min(tbl) == max(tbl)-1) break if(n > max_iter) break } return(t(map)) } a <- assignment(10,7,3) Dan Daniel Nordlund Bothell, WA USA
This is not really a combinatorial problem, I'll use small letters
instead of caps.
Arrange the r referees in a circle.
start <- 1
Replicate k times{
end <- (start + m-1)%% r
output: c(start,end)
start <- (end+1)%% r
}
Bert Gunter
Genentech Nonclinical Biostatistics
(650) 467-7374
"Data is not information. Information is not knowledge. And knowledge
is certainly not wisdom."
H. Gilbert Welch
On Wed, Apr 30, 2014 at 10:48 AM, Ravi Varadhan <ravi.varadhan at jhu.edu>
wrote:> Hi,
>
> I have this problem: K candidates apply for a job. There are R referees
available to review their resumes and provide feedback. Suppose that we would
like M referees to review each candidate (M < R). How would I assign
candidates to referees (or, conversely, referees to candidates)? There are two
important cases: (a) K > (R choose M) and (b) K < (R chooses M).
>
> Case (a) actually reduces to case (b), so we only have to consider case
(b). Without any other constraints, the problem is quite easy to solve. Here
is an example that shows this.
>
> require(gtools)
> set.seed(12345)
> K <- 10 # number of candidates
> R <- 7 # number of referees
> M <- 3 # overlap, number of referees reviewing each candidate
>
> allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE)
> assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE),
]
> assignment
>> assignment
> [,1] [,2] [,3]
> [1,] 3 4 5
> [2,] 3 5 7
> [3,] 5 6 7
> [4,] 3 5 6
> [5,] 1 6 7
> [6,] 1 2 7
> [7,] 1 4 5
> [8,] 3 6 7
> [9,] 2 4 5
> [10,] 4 5 7
>>
>
> Here each row stands for a candidate and the column stands for the referees
who review that candidate.
>
> Of course, there are some constraints that make the assignment challenging.
We would like to have an even distribution of the number of candidates reviewed
by each referee. For example, the above code produces an assignment where
referee #2 gets only 2 candidates and referee #5 gets 7 candidates. We would
like to avoid such uneven assignments.
>
>> table(assignment)
> assignment
> 1 2 3 4 5 6 7
> 3 2 4 4 7 4 6
>>
>
> Note that in this example there are 35 possible triplets of referees and 10
candidates. Therefore, a perfectly even assignment is not possible.
>
> I tried some obvious, greedy search methods but they are not guaranteed to
work. Any hints or suggestions would be greatly appreciated.
>
> Best,
> Ravi
>
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> 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.
Thank you, Dan and Bert. Bert - Your approach provides a solution. However, it has the undesired property of referees lumping together (I apologize that I did not state this as a condition). In other words, it does not "mix" the referees in some random fashion. Dan - your approach attempts to have the desired properties, but is not guaranteed to work. Here is a counterexample:> set.seed(1234) > a <- assignment(40,15,3) > table(a)a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 7 12 7 4 10 8 6 8 13 7 7 11 3 7 Notice that the difference between maximum and minimum candidates for referees is 13 - 3 = 10. Of course, I have to increase the # iters to get a better solution, but for large K and R this may not converge at all. Best regards, Ravi From: Ravi Varadhan Sent: Wednesday, April 30, 2014 1:49 PM To: r-help@r-project.org Subject: A combinatorial assignment problem Hi, I have this problem: K candidates apply for a job. There are R referees available to review their resumes and provide feedback. Suppose that we would like M referees to review each candidate (M < R). How would I assign candidates to referees (or, conversely, referees to candidates)? There are two important cases: (a) K > (R choose M) and (b) K < (R chooses M). Case (a) actually reduces to case (b), so we only have to consider case (b). Without any other constraints, the problem is quite easy to solve. Here is an example that shows this. require(gtools) set.seed(12345) K <- 10 # number of candidates R <- 7 # number of referees M <- 3 # overlap, number of referees reviewing each candidate allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE) assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ] assignment> assignment[,1] [,2] [,3] [1,] 3 4 5 [2,] 3 5 7 [3,] 5 6 7 [4,] 3 5 6 [5,] 1 6 7 [6,] 1 2 7 [7,] 1 4 5 [8,] 3 6 7 [9,] 2 4 5 [10,] 4 5 7>Here each row stands for a candidate and the column stands for the referees who review that candidate. Of course, there are some constraints that make the assignment challenging. We would like to have an even distribution of the number of candidates reviewed by each referee. For example, the above code produces an assignment where referee #2 gets only 2 candidates and referee #5 gets 7 candidates. We would like to avoid such uneven assignments.> table(assignment)assignment 1 2 3 4 5 6 7 3 2 4 4 7 4 6>Note that in this example there are 35 possible triplets of referees and 10 candidates. Therefore, a perfectly even assignment is not possible. I tried some obvious, greedy search methods but they are not guaranteed to work. Any hints or suggestions would be greatly appreciated. Best, Ravi [[alternative HTML version deleted]]
Ravi:
You cannot simultaneously have balance and guarantee random mixing.
That is, you would need to specify precisely what you mean by balance
and random mixing in this context, as these terms are now subjective
and undefined.
You could, of course, randomize the initial assignment of referees to
positions and note also that some mixing of referee groups would occur
if m does not divide r evenly. More explicitly, note that a very fast
way to generate the groups I described is:
rmk <- function(nrefs,size,ncands){
n <- ncands * size
matrix(rep(seq_len(nrefs), n %/% nrefs +1)[seq_len(n)],nrowncands,byrow=TRUE)
}
## corner case checks and adjustments need to be made to this, of course.
> rmk(7,3,10)
[,1] [,2] [,3]
[1,] 1 2 3
[2,] 4 5 6
[3,] 7 1 2
[4,] 3 4 5
[5,] 6 7 1
[6,] 2 3 4
[7,] 5 6 7
[8,] 1 2 3
[9,] 4 5 6
[10,] 7 1 2
You could then modify this by randomly reordering the referees every
time a complete cycle of the groupings occurred, i.e. after each
nrefs/gcd(nrefs,size) candidates = rows. This would give variable
groups and even assignment. This algorithm could be further fiddled
with by choosing nrefs and size to assure they are relatively prime
and then adding and removing further refs randomly during the cycling.
etc.
Cheers,
Bert
Bert Gunter
Genentech Nonclinical Biostatistics
(650) 467-7374
"Data is not information. Information is not knowledge. And knowledge
is certainly not wisdom."
H. Gilbert Welch
On Thu, May 1, 2014 at 6:09 AM, Ravi Varadhan <ravi.varadhan at jhu.edu>
wrote:> Thank you, Dan and Bert.
>
>
>
> Bert ? Your approach provides a solution. However, it has the undesired
> property of referees lumping together (I apologize that I did not state
this
> as a condition). In other words, it does not "mix" the referees
in some
> random fashion.
>
>
>
> Dan ? your approach attempts to have the desired properties, but is not
> guaranteed to work. Here is a counterexample:
>
>
>
>> set.seed(1234)
>
>> a <- assignment(40,15,3)
>
>> table(a)
>
> a
>
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
>
> 10 7 12 7 4 10 8 6 8 13 7 7 11 3 7
>
>
>
> Notice that the difference between maximum and minimum candidates for
> referees is 13 ? 3 = 10. Of course, I have to increase the # iters to get
a
> better solution, but for large K and R this may not converge at all.
>
>
>
> Best regards,
>
> Ravi
>
>
>
> From: Ravi Varadhan
> Sent: Wednesday, April 30, 2014 1:49 PM
> To: r-help at r-project.org
> Subject: A combinatorial assignment problem
>
>
>
> Hi,
>
>
>
> I have this problem: K candidates apply for a job. There are R referees
> available to review their resumes and provide feedback. Suppose that we
> would like M referees to review each candidate (M < R). How would I
assign
> candidates to referees (or, conversely, referees to candidates)? There are
> two important cases: (a) K > (R choose M) and (b) K < (R chooses M).
>
>
>
> Case (a) actually reduces to case (b), so we only have to consider case
(b).
> Without any other constraints, the problem is quite easy to solve. Here is
> an example that shows this.
>
>
>
> require(gtools)
>
> set.seed(12345)
>
> K <- 10 # number of candidates
>
> R <- 7 # number of referees
>
> M <- 3 # overlap, number of referees reviewing each candidate
>
>
>
> allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE)
>
> assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE),
]
>
> assignment
>
>> assignment
>
> [,1] [,2] [,3]
>
> [1,] 3 4 5
>
> [2,] 3 5 7
>
> [3,] 5 6 7
>
> [4,] 3 5 6
>
> [5,] 1 6 7
>
> [6,] 1 2 7
>
> [7,] 1 4 5
>
> [8,] 3 6 7
>
> [9,] 2 4 5
>
> [10,] 4 5 7
>
>>
>
>
>
> Here each row stands for a candidate and the column stands for the referees
> who review that candidate.
>
>
>
> Of course, there are some constraints that make the assignment challenging.
> We would like to have an even distribution of the number of candidates
> reviewed by each referee. For example, the above code produces an
> assignment where referee #2 gets only 2 candidates and referee #5 gets 7
> candidates. We would like to avoid such uneven assignments.
>
>
>
>> table(assignment)
>
> assignment
>
> 1 2 3 4 5 6 7
>
> 3 2 4 4 7 4 6
>
>>
>
>
>
> Note that in this example there are 35 possible triplets of referees and 10
> candidates. Therefore, a perfectly even assignment is not possible.
>
>
>
> I tried some obvious, greedy search methods but they are not guaranteed to
> work. Any hints or suggestions would be greatly appreciated.
>
>
>
> Best,
>
> Ravi
>
>
Ravi Varadhan <ravi.varadhan <at> jhu.edu> writes:> > Hi, > > I have this problem: K candidates apply for a job. There are R refereesavailable to review their resumes and> provide feedback. Suppose that we would like M referees to review eachcandidate (M < R). How would I assign> candidates to referees (or, conversely, referees to candidates)? Thereare two important cases: (a) K >> (R choose M) and (b) K < (R chooses M). > > Case (a) actually reduces to case (b), so we only have to consider case(b). Without any other constraints,> the problem is quite easy to solve. Here is an example that shows this. > > require(gtools) > set.seed(12345) > K <- 10 # number of candidates > R <- 7 # number of referees > M <- 3 # overlap, number of referees reviewing each candidate > > allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE) > assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ] > assignment > > assignment > [,1] [,2] [,3] > [1,] 3 4 5 > [2,] 3 5 7 > [3,] 5 6 7 > [4,] 3 5 6 > [5,] 1 6 7 > [6,] 1 2 7 > [7,] 1 4 5 > [8,] 3 6 7 > [9,] 2 4 5 > [10,] 4 5 7 > > >Isn't this the problem of constructing a balanced incomplete block design? The problem and an R package to handle it are described here: http://www.r-bloggers.com/generating-balanced-incomplete-block-designs-bibd/ As noted there, you cannot always get balance. A Google Scholar search on "balanced incomplete block design" will pop up many classical works on this problem. Maybe try the ExperimentalDesigns Task view. HTH, Chuck