# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment