R中大型稀疏线性规划问题原型验证与求解优化技术问询

我是熟悉线性规划（LP）与R语言的金融从业者，现有一个含15100个变量、9280个约束（所有x≥0）的线性规划问题，约束矩阵稀疏度约90%。因真实问题的数据收集与处理难度大，先构建同规模、同稀疏度的原型，测试个人PC（Windows 11系统，Intel I-7 1800MHz，14核，32GB RAM）能否在数小时内求解。

原型代码 #

nVariables <- 15100
nConstraints <- 9280

cvec <- rep(1, nVariables)
set.seed(101)
coeffs <- 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, 
                                           verbose = 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%元素为0以模拟稀疏性；右侧向量bvec为每行元素和加10，确保所有变量取1时满足约束，问题可行；已转换为sparseMatrix以优化内存与求解速度。

技术问题 #

1. 该原型是否合理？
2. 已尝试linprog::solveLP、Rglpk::Rglpk_solve_LP、Rsymphony::Rsymphony_solve_LP三个求解函数，均未在3小时内完成计算。已知内点算法适用于大型稀疏线性规划问题，请问这些函数是否采用该算法？有无更适配此问题的R包？该规模问题的大致求解时间预估是多少？
3. 在Windows机器上能否通过并行处理加速该问题的求解？

1. 原型合理性分析 #

原型核心设计是合理的：

• 稀疏度模拟准确：通过随机置0实现90%稀疏度，匹配真实问题结构特征
• 可行性保障：bvec设置为行和加10，确保x=1是可行解，避免无可行解的测试障碍
• 目标函数简洁：最大化变量和的设计，排除了特殊目标结构对求解器性能测试的干扰

但存在一处代码笔误：原代码中coeffs <- runif(runif(nVariables * nConstraints))会生成随机长度的向量，导致后续矩阵构建出错，应修正为coeffs <- runif(nVariables * nConstraints)。

2. 求解器算法与适配性问题 #

现有求解器的算法情况 #

• linprog::solveLP：默认使用单纯形法，不支持内点算法，对大型稀疏问题效率极低，不适用当前规模
• Rglpk::Rglpk_solve_LP：调用GLPK求解器，仅支持单纯形法和分支定界法（针对整数规划），无内置内点算法，处理大型稀疏LP能力有限
• Rsymphony::Rsymphony_solve_LP：调用SYMPHONY求解器，以单纯形法为主，虽支持稀疏优化，但面对1.5万变量的问题，单纯形法迭代次数过多，难以在3小时内完成

更适配的R包 #

推荐以下支持内点算法、针对大型稀疏LP优化的包：

• osqp：基于ADMM的内点类算法，专门处理稀疏凸优化，LP求解效率极高，可直接调用
• cvxr：凸优化建模框架，底层可调用osqp、ECOS等内点法求解器，适合结构化问题
• gurobi/cplex：商业求解器的R接口，内置高效内点算法与稀疏优化策略，是超大规模LP的最优选择，但需授权

求解时间预估 #

• 开源内点法求解器（如osqp）：在你的硬件配置下，预估求解时间为10-30分钟（取决于稀疏结构与数值稳定性）
• 商业求解器（如Gurobi）：可压缩至5-15分钟，其预处理与并行优化能力更强

3. Windows机器上的并行加速 #

LP求解的并行加速依赖求解器原生支持，而非R通用并行工具：

• 开源求解器中，osqp暂不支持多线程，但单线程效率已足够高；GLPK、SYMPHONY的并行支持有限，Windows环境下难以实现有效加速
• 商业求解器（Gurobi、CPLEX）的R接口支持多线程，可通过设置线程数参数（如Gurobi的Threads）利用14核CPU，显著缩短求解时间
• 注意：R通用并行包（如parallel）无法直接加速LP求解，因LP求解是单进程数值计算任务，需求解器原生支持多线程

内容的提问来源于stack exchange，提问作者rmacey