HiGHS 线性规划求解器实战从 20 行建模代码到生产级性能调优【免费下载链接】HiGHSLinear optimization software项目地址: https://gitcode.com/GitHub_Trending/hi/HiGHSHiGHS 线性规划求解器是一个 MIT 协议的开源 C 求解器同时覆盖线性规划LP、凸二次规划QP和混合整数规划MIP内置 presolve求解前自动削减问题规模的过程、单纯形法、内点法和分支定界框架不依赖任何第三方库。本文以 Python 接口为主线从跑通第一个模型讲起把建模、求解器选型、性能调优和生产环境中的模型交换逐一过一遍源码结构见highs/主目录示例代码集中在examples/目录。一条产线、两种产品、三台瓶颈设备先说清楚要解决的问题你负责产线排产产品 A 每件利润 30 元、产品 B 每件 25 元每单位 A 耗 1 单位原料、每单位 B 耗 2 单位原料每天只有 80 单位A 的日产能上限是 150 件。排产计划每周重排一次而 Excel 试凑法每次要花大半天还不敢保证全局最优。这就是最典型的 LP 场景也是 HiGHS 的主场。它的优势不在于功能全而在于默认配置下就能给出最优解且 presolve、单纯形、内点法、MIP 四条技术路线在同一个引擎里切换不需要换工具。装完highspy后你可以直接跳到下一节跑通第一个实例如果暂时只想了解它内部有哪些求解器仓库文档docs/src/solvers.md有一份完整清单。HiGHS Python 安装后5 分钟跑通第一个模型HiGHS 的 Python 包是highspy一条 pip 命令即可pip install highspy之后就是建模的三步曲声明变量、加约束、求解取解。下面这个例子对应开篇的排产问题注意显式给出下界为 0——HiGHS 变量的默认下界是负无穷不写的话求解器会认为产量可以是负数import highspy h highspy.Highs() inf highspy.kHighsInf # 默认下界是 -inf排产量不可能为负所以要显式钉住下界 h.addVars(2, lb[0.0, 0.0], ub[100.0, 150.0]) # 目标系数A 每件 30 元B 每件 25 元 h.changeColsCost(2, [0, 1], [30.0, 25.0]) # 原料约束 1*x1 2*x2 80右端写成上界 80 h.addRow(0.0, 80.0, 2, [0, 1], [1.0, 2.0]) h.run() info h.getInfo() print(状态:, h.modelStatusToString(h.getModelStatus())) print(最优目标值:, info.objective_function_value) sol h.getSolution() print(产量:, list(sol.col_value))输出大致是状态: HighsModelStatus.kOptimal 最优目标值: 2000 产量: [40.0, 20.0]run()背后发生的事presolve 先尝试削减问题然后调用默认求解器LP 默认是单纯形法最后把 primal 解写回getSolution()。getInfo()返回的objective_function_value是最优目标值simplex_iteration_count是迭代次数这两个字段后面调优时都会反复用到。这个接口对 LP、QP、MIP 是同一套区别只在建模时用什么变量类型。下面看命名建模语法以及把 MIP 也跑起来。从 LP 到 MIPHiGHS 混合整数规划建模教程对熟悉PuLP或scipy.optimize的人来说highspy最省适应成本的地方是它的表达式建模语法——变量可以直接参与、运算。仓库自带的家具厂经典例子完整版在examples/chip.py精简后长这样import highspy h highspy.Highs() h.silent() # 关掉求解日志只要结果 # 命名变量 目标系数一次声明后面可以直接用 x[Tables] 引用 x h.addVariables([Tables, SetsOfChairs], obj[10.0, 25.0]) h.addConstrs(x[Tables] 2*x[SetsOfChairs] 80, # 装配工时 x[Tables] 4*x[SetsOfChairs] 120, # 涂装工时) h.setMaximize() h.solve() print([h.variableValue(v) for v in x]) # 最优产量 print([h.variableDual(v) for v in x]) # 变量对偶简化成本 print([h.constrValue(c) for c in h.getConstrs()]) # 约束取到的值解完 LP 顺手能拿到对偶值影子价格这对原料涨价多少还值不值得外购这类决策问题直接可用。如果决策是选或不选就换成整数变量。highspy提供了addBinaries快捷方法0-1 背包问题十几行就能写完import highspy h highspy.Highs() h.silent() # 演示 setSolution 热启动时presolve 会改变问题规模、使传入的解对不上号 # 所以这个例子里先关掉 h.setOptionValue(presolve, off) x h.addBinaries(5) # 5 个 0-1 变量 h.addConstr((x * [4, 3, 1, 5, 4]).sum() 11) # 背包重量 h.maximize((x * [8, 5, 3, 11, 7]).sum()) # 物品价值 h.run() print(背包总价值:, h.getInfo().objective_function_value) # 22 # 分支定界支持热启动喂回一个已有解让搜索从它出发 h.clearSolver() # 清空求解状态保留模型 h.setSolution(h.getSolution()) h.run()setSolution在 MIP 求解器里并不常见它的价值在于业务系统里已有的启发式解可以作为初始可行解传入搜索不用从零开始。热启动之外MIP 子问题用什么求解器是下一个章节的选型问题。3 种求解策略怎么选LP 部分highspy默认走单纯形法solver choose时 LP 的默认就是它。想换路线直接改solver选项即可simplex、ipmHiPO 内点法、ipx、hipo。内点法在小问题上不一定占优但仓库文档里明确问题规模一大HiPO 的优势可以拉开一个数量级以上所以大规模稀疏 LP 值得试一次切换h.setOptionValue(solver, ipm) # 切到内点法HiPO h.setOptionValue(parallel, on) # 启用并行 h.setOptionValue(threads, 4) # 限制最多 4 个线程MIP 部分有一个专门的旋钮mip_lp_solver控制分支定界树中 LP 子问题的求解器simplex/ipm/hipo根节点没有基信息时它尤其有用。这些选项的完整说明见仓库文档docs/src/options/definitions.md每一项都带取值范围和默认值。参数怎么落到生产环境的配置文件里下面接着说。让求解更快的四个参数旋钮调优的顺序建议是默认配置跑一遍拿基线 → 一次只改一个参数 → 对比model_status、目标值和迭代/节点数的变化。乱改一堆参数只会让你分不清是谁起了作用。最常见的三种场景和对应旋钮问题特征建议旋钮原因大规模稀疏 LP单纯形迭代数很高solver ipm内点法迭代次数不随规模线性膨胀大 MIP且有时间限制presolve onmip_lp_solver ipm根节点和深节点松弛用内点法求解更快LP 反复报数值病态、容差超标微调kkt_tolerance控制可行性/最优性KKT判定阈值生产环境里参数通常放在选项文件中一次性生效。HiGHS 选项文件支持#注释、空行和--命令行风格的行# highs_options.txt # HiGHS 选项文件每行一个选项# 开头为注释 presolve on time_limit 3600 # 最多跑 1 小时超时返回当前最优解 threads 4 # 并行时最多用 4 个线程 solver choose # 让 HiGHS 按问题类型自选LP 默认单纯形 ranging off # 需要敏感性报告时再打开加载它只需一行h.passOptionsFile(highs_options.txt)参数调不动的时候多半是模型结构的问题——比如满是不参与任何约束的变量、约束右端项量级相差十亿倍。这种情况改参数没有用应该回到建模层面把冗余变量清掉、把量级对齐。参数和配置文件解决了怎么跑得快还有两件生产上绕不开的事模型怎么在系统之间传递以及解出来之后怎么利用对偶信息。模型读写、敏感性分析与多目标HiGHS 原生读 MPS 和 CPLEX 风格 LP 文件求解后也能把模型写回磁盘适合在建模脚本 → 求解服务 → 结果归档的链路里做模型快照# 读入已有模型并求解 h2 highspy.Highs() h2.readModel(model.lp) h2.run() # 求解后把模型归档便于事后复盘当时到底解的是什么 h2.writeModel(model_archive.mps)对 LP 的决策者来说比最优解本身更值钱的是解有多稳健。打开ranging选项后HiGHS 会一次算出目标系数、变量边界、约束右端项各自允许变化多少而不改变当前最优基# highs_options.txt在上一节的基础上追加 ranging on多目标优化 HiGHS 也能接多个目标按权重加权成单目标求解权重变化时重新求解即可对比方案。到这里建模、求解、调优、交换的闭环就完整了。从哪里继续仓库里的check/目录有一整套测试用例和实例文件LP、MPS 混合含issue-*.mps这类回归用例examples/里还有网络流、多目标、回调callback等更多完整脚本可以直接拿来当模板改。如果你下一步的计划是处理含整数变量的排产或选址问题建议从 MIP 建模的完整案例读起需要嵌入自有 C 服务时C 接口头文件在highs/interfaces/highs_c_api.h示例程序见examples/call_highs_from_c.c。【免费下载链接】HiGHSLinear optimization software项目地址: https://gitcode.com/GitHub_Trending/hi/HiGHS创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考