求解超稀疏大规模LP问题：免费方法与代码推荐（支持可行解启动）

适用求解方法 #

针对你提到的10万-50万变量、约束仅关联2-3个变量的超稀疏LP问题，推荐以下方法：

• 对偶单纯形法：适配稀疏约束结构，对偶问题规模更小，能有效利用稀疏性降低计算开销
• 稀疏内点法：处理大规模LP的经典方案，收敛速度快，专为稀疏矩阵优化计算逻辑，适合变量量级极大的场景
• Dantzig-Wolfe分解：利用约束的稀疏关联特性拆分问题为子问题与主问题，适合可分组的变量结构，降低单步计算复杂度
• ADMM（交替方向乘子法）：可将大规模问题拆解为易求解的子问题，支持并行计算，适配分布式求解场景

免费代码工具 #

• CLP（COIN-OR Linear Programming）：COIN-OR开源LP求解器，深度优化稀疏矩阵处理，支持单纯形与内点法，可处理百万级变量。提供C++原生接口，也能通过Python的pyscipopt或cyipopt间接调用
• SCIP：虽主打混合整数规划，但LP模块对稀疏大规模问题处理高效，支持多算法切换，Python接口pyscipopt可直接调用其LP求解功能
• HiGHS：新一代开源LP/MIP求解器，针对稀疏问题做了专项优化，性能突出。支持C++、Python（highspy）接口，轻松应对百万级变量规模
• CVXPY：Python优化建模框架，可对接CLP、HiGHS等稀疏求解器，自动处理稀疏矩阵，适合快速建模验证
• Pyomo：Python优化建模库，支持连接CLP、SCIP等开源求解器，适配复杂问题的建模与大规模求解需求

支持初始可行解启动的工具 #

以下工具均支持从用户提供的已知可行解启动求解：

• CLP：通过API直接传入变量初始值，求解器会以此为起点迭代
• SCIP：建模阶段可设置变量初始值，LP模式下能利用初始可行解加速收敛
• HiGHS：提供设置初始基或变量初始值的接口，支持用户指定可行解作为起点
• CVXPY：通过variable.value = initial_value设置初始解，底层支持该功能的求解器会自动使用此初始值

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