Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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
You can’t perform that action at this time.