MIP (ompr) 模型在 R 中花费太多时间来解决
MIP (ompr) model taking too much time to solve in R
我正在尝试解决 R 中的容量限制设施位置问题。该示例数据:
n<- 500 #number of customers
m<- 20 #number of facility centers
set.seed(1234)
fixedcost <- round(runif(m, min=5000, max=10000))
warehouse_locations <- data.frame(
id=c(1:m),
y=runif(m, 22.4, 22.6),
x= runif(m, 88.3, 88.48)
)
customer_locations <- data.frame(
id=c(1:n),
y=runif(n, 22.27, 22.99),
x= runif(n, 88.12, 88.95)
)
capacity <- round(runif(m, 1000, 4000))
demand <- round(runif(n, 5, 50))
具有成本函数的模型:
library(geosphere)
transportcost <- function(i, j) {
customer <- customer_locations[i, ]
warehouse <- warehouse_locations[j, ]
(distm(c(customer$x, customer$y), c(warehouse$x, warehouse$y), fun = distHaversine)/1000)*20
}
library(ompr)
library(magrittr)
model <- MIPModel() %>%
# 1 iff i gets assigned to SC j
add_variable(x[i, j], i = 1:n, j = 1:m, type = "binary") %>%
# 1 if SC j is built
add_variable(y[j], j = 1:m, type = "binary") %>%
# Objective function
set_objective(sum_expr(transportcost(i, j) * x[i, j], i = 1:n, j = 1:m) +
sum_expr(fixedcost[j] * y[j], j = 1:m), "min") %>%
#Demand of customers shouldn't exceed total facility capacities
add_constraint(sum_expr(demand[i] * x[i, j], i = 1:n) <= capacity[j] * y[j], j = 1:m) %>%
# every customer needs to be assigned to a SC
add_constraint(sum_expr(x[i, j], j = 1:m) == 1, i = 1:n) %>%
# if a customer is assigned to a SC, then this SC must be built
add_constraint(x[i,j] <= y[j], i = 1:n, j = 1:m)
model
library(ompr.roi)
library(ROI.plugin.glpk)
result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))
目前正在对结果进行计算。
有什么方法可以减少计算时间吗?如果我理解正确,那么 0.4% 就是当前模型与期望结果之间的差异。就算相差远不止于此,我也会很高兴,我能得到一个合适的模型。有什么办法可以设置吗?大概 5-6% 的差异就足够了。
您可以尝试以下3种方法
- 您可以通过重新制定最后一个约束来进行测试。
如果客户被分配到一个 SC,那么这个 SC 必须被构建
您可以使用以下代替当前约束
add_constraint(sum_expr(x[i,j], i = 1:n)<= y[j], j = 1:m)
这应该会减少 运行 时间而不影响输出。
除此之外,您可以根据所需的最小最优性差距添加终止标准 or/and 您希望模型达到 运行 的最大 运行 时间。
您也可以尝试使用其他求解器代替 glpk,看看它是否有帮助。
R 和 Python 库对于 MIP 来说非常慢
尝试使用 lp solve 开源求解器
从@Erwin Kalvelagen 的评论中获得了帮助。使用 symphony 求解器并编辑了一行:
library(ROI.plugin.symphony)
result <- solve_model(model, with_ROI(solver = "symphony",
verbosity=-1, gap_limit=1.5))
处理时间减少很多,得到答案!
我正在尝试解决 R 中的容量限制设施位置问题。该示例数据:
n<- 500 #number of customers
m<- 20 #number of facility centers
set.seed(1234)
fixedcost <- round(runif(m, min=5000, max=10000))
warehouse_locations <- data.frame(
id=c(1:m),
y=runif(m, 22.4, 22.6),
x= runif(m, 88.3, 88.48)
)
customer_locations <- data.frame(
id=c(1:n),
y=runif(n, 22.27, 22.99),
x= runif(n, 88.12, 88.95)
)
capacity <- round(runif(m, 1000, 4000))
demand <- round(runif(n, 5, 50))
具有成本函数的模型:
library(geosphere)
transportcost <- function(i, j) {
customer <- customer_locations[i, ]
warehouse <- warehouse_locations[j, ]
(distm(c(customer$x, customer$y), c(warehouse$x, warehouse$y), fun = distHaversine)/1000)*20
}
library(ompr)
library(magrittr)
model <- MIPModel() %>%
# 1 iff i gets assigned to SC j
add_variable(x[i, j], i = 1:n, j = 1:m, type = "binary") %>%
# 1 if SC j is built
add_variable(y[j], j = 1:m, type = "binary") %>%
# Objective function
set_objective(sum_expr(transportcost(i, j) * x[i, j], i = 1:n, j = 1:m) +
sum_expr(fixedcost[j] * y[j], j = 1:m), "min") %>%
#Demand of customers shouldn't exceed total facility capacities
add_constraint(sum_expr(demand[i] * x[i, j], i = 1:n) <= capacity[j] * y[j], j = 1:m) %>%
# every customer needs to be assigned to a SC
add_constraint(sum_expr(x[i, j], j = 1:m) == 1, i = 1:n) %>%
# if a customer is assigned to a SC, then this SC must be built
add_constraint(x[i,j] <= y[j], i = 1:n, j = 1:m)
model
library(ompr.roi)
library(ROI.plugin.glpk)
result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))
目前正在对结果进行计算。
有什么方法可以减少计算时间吗?如果我理解正确,那么 0.4% 就是当前模型与期望结果之间的差异。就算相差远不止于此,我也会很高兴,我能得到一个合适的模型。有什么办法可以设置吗?大概 5-6% 的差异就足够了。
您可以尝试以下3种方法
- 您可以通过重新制定最后一个约束来进行测试。
如果客户被分配到一个 SC,那么这个 SC 必须被构建
您可以使用以下代替当前约束 add_constraint(sum_expr(x[i,j], i = 1:n)<= y[j], j = 1:m)
这应该会减少 运行 时间而不影响输出。
除此之外,您可以根据所需的最小最优性差距添加终止标准 or/and 您希望模型达到 运行 的最大 运行 时间。
您也可以尝试使用其他求解器代替 glpk,看看它是否有帮助。
R 和 Python 库对于 MIP 来说非常慢 尝试使用 lp solve 开源求解器
从@Erwin Kalvelagen 的评论中获得了帮助。使用 symphony 求解器并编辑了一行:
library(ROI.plugin.symphony)
result <- solve_model(model, with_ROI(solver = "symphony",
verbosity=-1, gap_limit=1.5))
处理时间减少很多,得到答案!