我已经概述了一个线性规划问题,它有大约15100个变量(未知数)和9280个约束(所有x>=0)。约90%的约束矩阵将是稀疏的。由于数据收集和操作的挑战,对现实世界问题的设置进行编码将花费很长时间。在尝试之前,我先用一个原型做实验。原型的目的是看看我的PC是否能在几个小时内解决这种大小的问题。原型的代码如下。我有几个问题:
- 原型是否合理?它的大小相同,它的约束矩阵具有类似于我所设想的稀疏性。
- 我尝试了三个优化函数:linprog::solveLP; RglpK::Rglpk_solve_LP;和Rsymphony::Rsymphony_solve_LP。没有人在3小时内解决了这个问题。我的阅读表明,内点算法在解决稀疏矩阵的大型问题时很有用。这些函数中是否有使用此算法的?是否有其他软件包更适合我的问题?(我读过Google's Guide on Advanced LP Solving和这个benchmarking study以及有用的Sandia report Comparison of open-source linear programming。从阅读这些,我会认为3个小时就足够了。对它所需的时间有什么粗略的估计吗?
- 有没有办法在Windows机器上使用并行处理来加速这个问题?
nVariables <- 15100
nConstraints <- 9280
cvec <- rep(1, nVariables)
set.seed(101)
coeffs <- runif(runif(nVariables * nConstraints))
coeffs[sample(nVariables * nConstraints,
0.9 * nVariables * nConstraints,
replace = FALSE)] <- 0
Amat <- matrix(coeffs, nrow = nConstraints, ncol = nVariables)
bvec <- apply(Amat, 1, sum) + 10
rm(coeffs)
library(Matrix)
sparseAmat <- as(Amat, "sparseMatrix")
save(sparseAmat, bvec, cvec, nVariables, nConstraints, file = "sparsevecs.rdata")
timeLimit <- 1000 * 60 * 60 * 3 # 3 hours in millisecs
library(linprog)
library(R.utils)
print("starting solveLP")
print(Sys.time())
withTimeout(system.time(testSolveLP <- solveLP(cvec, bvec, sparseAmat, maximum = TRUE)),
timeout = timeLimit/1000, onTimeout = "warning")
print(Sys.time())
library(Rglpk)
print("starting Rglpk_solve_LP")
print(Sys.time())
testRglpk <- Rglpk_solve_LP(cvec, sparseAmat, dir = rep("<=", nConstraints), rhs = bvec,
max = TRUE,
control = list(tm_limit = timeLimit,
presolve = FALSE,
vebose = TRUE))
print(Sys.time())
library(Rsymphony)
print("starting Rsymphony")
print(Sys.time())
testRSymphony <- Rsymphony_solve_LP(cvec, sparseAmat, dir = rep("<=", nConstraints),
rhs = bvec, max = TRUE,
time_limit = timeLimit/1000)
print(Sys.time())
下面是上面代码背后的思想。'cvec'是目标向量,并且都是1。这个问题只是使这些值的和最大化。系数矩阵'Amat'是随机均匀值,其中90%被零替换以使其稀疏。右侧值('bvec')是每行中的值的总和加上10。因此,每个变量的值1应满足每个约束的条件。因此,该问题是可行的。我使用了一个稀疏矩阵('sparseAmat'),希望这样可以减少内存并加快求解速度。这是在尝试使用基础版本“Amat”之后。
我是一个熟悉线性规划和R的金融专业人士。我使用的是Windows 11,英特尔I-7 1800 Mhz,14核,32 GB RAM。谢谢你的帮助。
1条答案
按热度按时间dced5bon1#
FWIW,这里有几个使用python的
scipy.optimize
作为建模框架的相同问题的基准测试,现在使用(默认情况下)(新的)开源求解器HiGHS
,根据我的经验,这已经证明是相当不错的。我不是scipy.optimize
的常规用户,但对于像这样具有自然矩阵公式的问题,它非常方便。我在解决部分或完全由随机值/系数生成的大型问题方面的有限经验是,LP和ILP的速度相当慢。基本上要求求解器解决“噪声”,这需要大量的迭代。我使用了一个
cvec
,它是范围[1,n_var
]的随机分布。使用“ones”cvec
从来没有走得太远。我还尝试了两种类型的b_vec
,一种和你一样,另一种是随机整数,我认为这大大降低了求解的复杂性,尽管我没有过多地探索。TL;DR:相同维度和稀疏性问题的结果:
b_vec
b_vec
编码(
python
):结果(随机
b_vec
):结果(您的
b_vec
):