MIP (ompr)模型在R中的求解时间过长

Question

我正试图解决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%的差别就足够了。

Answer 1

接受了@Erwin Kalvelagen评论的帮助。使用交响乐解说器并编辑一行：

library(ROI.plugin.symphony)
result <- solve_model(model, with_ROI(solver = "symphony",
                                      verbosity=-1, gap_limit=1.5))

处理时间大大缩短，得到了答案！

Answer 2

您可以尝试以下3种方法

1. 您可以通过重新制定最后一个约束来进行测试。

如果客户被分配给SC，则必须构建这个SC。

您可以使用以下方法来代替当前约束add_constraint(sum_expr(xi，j，i= 1:n)<= yj，j= 1:m)

这将在不影响输出的情况下减少运行时间。

1. 除此之外，您还可以根据所需的最小最优性差距或/和运行模型的最大运行时间添加终止条件。

1. ，您也可以尝试使用其他的解算器，而不是glpk，这样会有所帮助。

Answer 3

R和Python库对于MIP来说非常慢，可以尝试使用lp解决开源解决程序。