In jlepird/raml: Algebraic Modeling Language for Linear and Integer Programs

This vignette demonstrates how to use the raml package to solve a simple scheduling problem: twelve representatives attend a conference, and each representative needs to meet every other representative one on one. How can we most efficiently schedule this conference?

To begin, we define the model object:

library(raml)

m <- Model()
m$sense <- "min"

Now, we define our decision variables: should representative i meet with representative j during time period k?

m$var(x[1:12, 1:12, 1:20] >= 0, "Binary")

We know that if i is meeting with j, then j must also be meeting with i:

for (k in 1:20) { 
  for (i in 1:12) {
    for (j in 1:i) {
      m$constraint(x[i, j, k] == x[j, i, k])
    }
  }
}

Furthermore, each representative can only meet with one other representative during a given time frame:

for (k in 1:20) {
  for (i in 1:12) {
    m$constraint(rsum(x[i,j_i,k], j_i = 1:12) <= 1)
  }
}

Now, we require every representative meet with every other representative:

for (i in 1:12) {
  for (j in 1:12) {
    if (i != j) {
      m$constraint(rsum(x[i,j,k_i], k_i = 1:20) >= 1)
    }
  }
}

We define our objective function to minimize the amount of time everyone has to spend at the conference:

gamma <- 1.1
m$objective(rsum(gamma^k_i * x[i_i, j_i, k_i], i_i = 1:12, j_i = 1:12, k_i = 1:20))

Finally, we can solve the model:

m$solve()

Now, we can visualize the meetings:

df <- data.frame(i = numeric(), j = numeric(), k = numeric())
for (i in 1:12) {
  for (j in 1:12) {
    for (k in 1:20) {
      if (value(x[i,j,k]) > 0) {
        df <- rbind(df, data.frame(i = i, j = j, k = k))
      }
    }
  }
}
library(ggplot2)
ggplot(df, aes(i,j, label = k)) + 
  geom_text() + 
  scale_x_continuous("Rep i", breaks = 1:12) + 
  scale_y_continuous("Rep j", breaks = 1:12)