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

Question

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

#需求文件需求-4821个(DPP(销售点(D(的需求

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包来优化运输材料以满足需求。这可能是一个非常简单的运输问题，但需要花费大量时间。我使用的是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

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

1. 请确保使用ompr和listcomp的最新CRAN版本
2. 尝试使用filter conditions仅创建/使用与模型相关的变量，而不是添加所有nrow(LCMat)*ncol(LCMat)变量，然后(可能(将其中许多变量设置为0。有关示例，请参阅下面的代码。根据你的问题有多稀疏，这也会有所帮助

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

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

^{创建于2022-03-12由reprex包(v2.0.1(}

Answer 2

• 对于大型模型，OMPR和GLPK都很慢
• 您正在复制sum_over(x[i,j], j = 1:ncol(LCMat))。这会导致非零元素的数量超过所需数量。我通常会试图防止这种情况发生(即使是以牺牲更多变量为代价(