Assigning judges to entries using linear programming in R

63 Views Asked by At

I want to assign 4 judges to mark 15 entries, such that:

  1. Each entry is marked by exactly 2 judges;
  2. Each judge marks an equal number of entries (or close to equal given that the number of entries is not divisible by the number of judges - in this case 2 judges should have 7 and 2 judges should have 8); and
  3. The number of entries shared by any 2 judges is equal for all combinations of judges (or close to equal - in this case each unique judge pair should have either 2 or 3 cases between them)

Using the answer provided in this question Randomly assign elements repeatedly to a limited number of groups, I was able to use lpSolve to assign entries in a way that satisfies criteria 1 and 2. But as you can see, it does not satisfy criterion 3 e.g. judges S+J mark 4 entries together, while judges S+T mark 2 together.

How can I add this criterion as a further constraint to the code?

library(lpSolve)
set.seed(144)

N <- c('T','E','S','J')
M <- 1:15

vars <- expand.grid(i=M, j=N)
mod <- lp(direction = "max",
          objective.in = rnorm(nrow(vars)),
          const.mat = rbind(t(sapply(M, function(i) as.numeric(vars$i == i))),
                            t(sapply(N, function(j) as.numeric(vars$j == j)))),
          const.dir = rep(c("=", "<="), c(length(M), length(N))),
          const.rhs = rep(c(2, 8), c(length(M), length(N))), 
          all.bin = TRUE)

# Extract all cases assigned to each judge
sapply(N, function(j) vars$i[mod$solution > 0.999 & vars$j == j])

$T
[1]  2  9 10 11 12 13 15

$E
[1]  5  7  8  9 11 12 14 15

$S
[1]  1  3  4  5  6 10 13 14

$J
[1] 1 2 3 4 6 7 8
0

There are 0 best solutions below