使用 OMPR 对大型数据集进行运输成本优化

Question

我正在解决给定一组约束的运输优化问题。以下是我掌握的三个关键数据集

#需求文件需求 - 在 4821(DPP) 个销售点 (D) 有需求 (DEMAND)

head(demand)
                       D        PP DEMAND                             DPP
1 ADILABAD (V) - T:11001  OPC:PACK 131.00 ADILABAD (V) - T:11001:OPC:PACK
2 ADILABAD (V) - T:13003  OPC:PACK 235.00 ADILABAD (V) - T:13003:OPC:PACK
3  ADILABAD (V) - T:2006  PPC:PACK  30.00  ADILABAD (V) - T:2006:PPC:PACK
4  ADILABAD (V) - T:4001  OPC:PACK  30.00  ADILABAD (V) - T:4001:OPC:PACK
5  ADILABAD (V) - T:7006 OPC:NPACK  34.84 ADILABAD (V) - T:7006:OPC:NPACK
6         AHMEDABAD:1001  OPC:PACK 442.10         AHMEDABAD:1001:OPC:PACK

#容量文件 cc - 在 1823 个源 (SOURCE) 中有容量限制 (MaxP, MinP)

head(cc,4)
                     SOURCE MinP  MaxP
1 CHILAMKUR:P:OPC:NPACK:0:R  900 10806
2 CHILAMKUR:P:OPC:NPACK:0:W  900 10806
3  CHILAMKUR:P:OPC:PACK:0:R 5628 67536
4  CHILAMKUR:P:OPC:PACK:0:W 5628 67536

#LandingCost 文件 LCMat - 这是一个矩阵，其中包含从给定来源 (SOURCE) 跨需求位置 (DPP) 交付产品的着陆成本。这是一个 1823 x 4821 矩阵。由于给定来源不存在所有位置的着陆成本，因此我已将其替换为此类 DPP 的巨大成本 (10^6)。

我正在使用 R 中的 OMPR 包来优化运输 material 以满足需求。这可能是一个非常简单的传输问题，但要花费很多时间。我使用的是 16GB 内存机器

代码如下。谁能指导我应该如何做得更好？

a = Sys.time()
grid = expand.grid(i = 1:nrow(LCMat),j = 1:ncol(LCMat))
grid_solve = grid[which(LCMat < 10^6),]
grid_notsolve = grid[which(LCMat >= 10^6),]

model <- MILPModel() %>% 
  add_variable(x[grid$i, grid$j],lb = 0, type = "continuous") %>%
  add_constraint(x[grid_notsolve$i, grid_notsolve$j] == 0) %>%
  add_constraint(sum_over(x[i,j], i = 1:nrow(LCMat)) <= demand$DEMAND[j], j = 1:ncol(LCMat)) %>%
  add_constraint(sum_over(x[i,j], j = 1:ncol(LCMat)) <= cc$MaxP[i], i = 1:nrow(LCMat)) %>%
  add_constraint(sum_over(x[i,j], j = 1:ncol(LCMat)) >= cc$MinP[i], i = 1:nrow(LCMat)) %>%
  set_objective(sum_expr(LCMat[grid_solve$i,grid_solve$j]*x[grid_solve$i,grid_solve$j]),"min")

solution = model %>% solve_model(with_ROI(solver = "glpk", verbose = TRUE))
Sys.time() - a

Answer 1

对于大型模型，OMPR 和 GLPK 都很慢。
您正在复制 sum_over(x[i,j], j = 1:ncol(LCMat))。这导致了比需要更多的非零元素。我通常会尽量避免这种情况（即使以牺牲更多变量为代价）。

Answer 2

两个可能加快速度的选项：

确保您使用 ompr 和 listcomp 的最新 CRAN 版本。
尝试仅将 filter conditions 用于与模型相关的 create/use 变量，而不是添加所有 nrow(LCMat)*ncol(LCMat) 变量，然后（可能）将其中很多设置为 0 . 示例见下面的代码。这也可能会有所帮助，具体取决于您的问题有多稀疏。

以下代码采用稀疏矩阵（即在您的情况下具有许多 0 元素或 10^6 元素的矩阵）并且仅生成 x[i,j] 在 sparse_matrix 中具有条目的变量大于 0。它有望说明如何使用该功能并将其应用于您的案例。

library(ompr)
sparse_matrix <- matrix(
  c(
    1, 0, 0, 1,
    0, 1, 0, 1,
    0, 0, 0, 1,
    1, 0, 0, 0
  ), byrow = TRUE, ncol = 4
)
is_connected <- function(i, j) {
  sparse_matrix[i, j] > 0
}
n <- nrow(sparse_matrix)
m <- ncol(sparse_matrix)
model <- MIPModel() |> 
  add_variable(x[i, j], i = 1:n, j = 1:m, is_connected(i, j)) |> 
  set_objective(sum_over(x[i, j], i = 1:n, j = 1:m, is_connected(i, j))) |> 
  add_constraint(sum_over(x[i, j], i = 1:n, is_connected(i, j)) <= 1, j = 1:m)

variable_keys(model)
#> [1] "x[1,1]" "x[1,4]" "x[2,2]" "x[2,4]" "x[3,4]" "x[4,1]"

extract_constraints(model)
#> $matrix
#> 3 x 6 sparse Matrix of class "dgCMatrix"
#>                 
#> [1,] 1 . . . . 1
#> [2,] . . 1 . . .
#> [3,] . 1 . 1 1 .
#> 
#> $sense
#> [1] "<=" "<=" "<="
#> 
#> $rhs
#> [1] 1 1 1

^{由 reprex package (v2.0.1)}

于 2022 年 3 月 12 日创建

使用 OMPR 对大型数据集进行运输成本优化

Transportation cost optimisation using OMPR for a large data set

optimization

routes

bigdata

operations-research

ompr