ompr-benchmark.R

# based on the formulation from here
# http://wwwhome.math.utwente.nl/~uetzm/do/IP-FKS.pdf
library(magrittr)
# devtools::install_github("dirkschumacher/ompr@milp")
library(ompr)

max_colors <- 10
n <- 100

# variables n * max_colors
# constraints: n^2 * max_colors + n + max_colors
print(n * max_colors)
print(n^2* max_colors + n + max_colors)

# the new backend
# currently called MILPModel - L for linear
# it hase slightly different semantics than the initial backend, but is consitent (vectorize all the things)
system.time(
  {
    model <- MILPModel() %>%

      # 1 iff node i has color k
      add_variable(x[i, k], type = "binary", i = 1:n, k = 1:max_colors) %>%

      # 1 iff color k is used
      add_variable(y[k], type = "binary", k = 1:max_colors) %>%

      # minimize colors
      # multiply by k for symmetrie breaking (signifcant diff. in solution time)
      set_objective(sum_expr(k * y[k], k = 1:max_colors), sense = "min") %>%

      # each node is colored
      add_constraint(sum_expr(x[i, k], k = 1:max_colors) == 1, i = 1:n) %>%

      # if a color k is used, set y[k] to 1
      add_constraint(sum_expr(x[i, k], i = 1:n) <= n * y[k], k = 1:max_colors) %>%

      # no adjacent nodes have the same color
      # for this test, we assume every node is adjacent to all others
      add_constraint(x[i, k] + x[j, k] <= 1, i = 1:n, j = 1:n, k = 1:max_colors)
    extract_constraints(model) # simulates passing it to a solver
    objective_function(model)
  }
)

# on my computer
# Mixed linear integer optimization problem
# Variables:
#   Continuous: 0
# Integer: 0
# Binary: 1010
# Model sense: minimize
# Constraints: 100110
# user  system elapsed
# 0.834   0.030   0.871

# the old backend
system.time(
  {
    model <- MIPModel() %>%

      # 1 iff node i has color k
      add_variable(x[i, k], type = "binary", i = 1:n, k = 1:max_colors) %>%

      # 1 iff color k is used
      add_variable(y[k], type = "binary", k = 1:max_colors) %>%

      # minimize colors
      # multiply by k for symmetrie breaking (signifcant diff. in solution time)
      set_objective(sum_expr(k * y[k], k = 1:max_colors), sense = "min") %>%

      # each node is colored
      add_constraint(sum_expr(x[i, k], k = 1:max_colors) == 1, i = 1:n) %>%

      # if a color k is used, set y[k] to 1
      add_constraint(sum_expr(x[i, k], i = 1:n) <= n * y[k], k = 1:max_colors) %>%

      # no adjacent nodes have the same color
      # for this test, we assume every node is adjacent to all others
      add_constraint(x[i, k] + x[j, k] <= 1, i = 1:n, j = 1:n, k = 1:max_colors)
    extract_constraints(model) # simulates passing it to a solver
    objective_function(model)
  }
)

# on my computer
# Mixed linear integer optimization problem
# Variables:
#   Continuous: 0
# Integer: 0
# Binary: 1010
# Model sense: minimize
# Constraints: 100110
# user  system elapsed
# 708.670  65.669 799.387