如何在scipy线性规划中处理复杂约束并优化内存占用？

关于linprog求解器与minimize的搭配、linprog自定义约束的问题 #

• 没法用linprog的低内存求解器搭配minimize：minimize的接口是针对非线性优化设计的，而linprog的求解器（如highs系列）只支持线性目标和线性约束，两者的接口规范、求解逻辑不兼容，无法直接混用。
• linprog不支持自定义函数约束：linprog的核心是线性规划求解器，仅接受矩阵形式的线性等式/不等式约束（A_ub x ≤ b_ub、A_eq x = b_eq），任何非线性的自定义约束都无法被其处理。

千万级规模线性问题的入手方向（避免非线性解法） #

1. 优先将“复杂约束”线性化 #

大部分看似复杂的约束都能转化为线性形式：

• 比如你示例中的sum(x) - 1000 ≤ 0，本质就是线性约束，直接用全1的行向量作为A_ub，b_ub设为1000即可，完全不需要自定义函数。
• 对于分段线性、绝对值、逻辑判断类约束，可以通过引入辅助变量转化为线性约束。例如|x_i - x_j| ≤ c可拆分为x_i - x_j ≤ c和x_j - x_i ≤ c两个线性不等式。

2. 用linprog的高效求解器+稀疏矩阵优化内存 #

千万级规模下，内存优化的关键是用稀疏矩阵存储约束：

• scipy的linprog默认使用的highs求解器原生支持稀疏矩阵，能大幅降低内存占用（稀疏矩阵仅存储非零元素，千万级稀疏矩阵的内存占用可能只有稠密矩阵的几十分之一）。
• 示例代码改造（适配linprog）：

import scipy.optimize as opt
import scipy.sparse as sp

solution_length = 10**7  # 千万级变量规模
coefficients = # 你的目标系数，建议用numpy数组或稀疏向量
# 构造sum(x) ≤ 1000的线性约束（稀疏矩阵形式）
A_ub = sp.csr_matrix([[1]*solution_length])
b_ub = [1000]
bounds = [(0, 1)] * solution_length

# 调用linprog求解
results = opt.linprog(c=coefficients, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

3. 若约束无法线性化，考虑大规模MIP工具 #

如果确实存在无法转化为线性的约束，可选择支持大规模问题的混合整数规划（MIP）工具：

• 开源工具如SCIP，商业工具如Gurobi、CPLEX，它们支持自定义约束（通过回调或建模接口），且针对大规模优化做了内存和速度优化。但优先还是尝试线性化，因为MIP求解速度通常慢于纯线性规划。

4. 其他内存优化技巧 #

• 避免预先生成全量稠密矩阵，利用循环或生成器构造稀疏矩阵，只存储非零元素。
• 若约束存在重复结构，可复用约束模板，减少冗余存储。

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