HiGHS求解器实战：30行代码解出最优排班

HiGHS求解器实战：30行代码解出最优排班

【免费下载链接】HiGHSLinear optimization software项目地址: https://gitcode.com/GitHub_Trending/hi/HiGHS

周日晚上，排班组长还在手工调整值班表：明天有人请假谁来顶？夜班少一个人安全吗？牵一发动全身，手工试错总会顾此失彼——这正是 HiGHS 求解器这类线性规划求解工具几秒内就能给出答案的问题。

HiGHS 一览：能解什么问题、怎么装

HiGHS 求解器是一个高性能的串行与并行线性优化求解器，主体用 C++ 编写，不依赖任何第三方库。它覆盖三类问题，标准形式是min ½xᵀQx + cᵀx, s.t. L ≤ Ax ≤ U, l ≤ x ≤ u，其中 Q 半正定；Q 为零且部分变量取整时就是整数问题。

一条 pip 命令装好 HiGHS，三行代码跑通第一次线性规划求解

第 1 步，安装 Python 包（会自动带上依赖的 numpy）：

pip install highspy

第 2 步，三行代码读一个现成的 LP 模型并求解：

import highspy h = highspy.Highs() h.readModel("check/instances/smalllp.mps") # 仓库自带的小样例 h.run()

第 3 步，把结果拿出来：

print(h.getModelStatus()) # kOptimal 表示找到最优解 print(h.getInfo().objective_function_value) # 最优目标值

如果要做 MIP 求解器安装、编译出命令行工具，或者想从源码改起，在仓库里执行下面两条命令即可（需要 CMake 3.15 及以上），会生成可执行文件bin/highs和库lib/highs；也可以在源码根目录直接pip install .从源码构建 Python 包：

git clone https://gitcode.com/GitHub_Trending/hi/HiGHS cd HiGHS && cmake -S . -B build && cmake --build build

打个比方：LP、QP、MIP 分别是什么，求解器内部做了什么

LP（线性规划）像一块多面体形状的倾斜滑板：可行区域是凸多面体，目标函数就是重力，最优解一定落在某个顶点上。单纯形法干的事就是从顶点滑到顶点，直到滑不动为止。

QP（二次规划）相当于滑板面变弯了：目标函数是一个抛物面，任务变成在碗状山谷里找最低点。约束是 Q 必须半正定——曲面只能凸，不能凹，否则存在多个局部最优，HiGHS 不接受这种问题。

MIP（混合整数规划）是最贴近业务的一类：变量必须站在整数格点上，"0.7 个护士"是不存在的。求解策略是先把整数约束放掉、当 LP 解，得到一个"下界"，再用分支定界把变量一刀一刀切开，把"不可能比当前最优更好"的分支剪掉，辅以割平面把松弛解往整数格点上推。

不管哪类问题，h.run()之后的调用链大致是四步：

1. 预处理（presolve）：先修题。把没有自由的变量定死、删掉冗余约束、检查矛盾——很多无可行解问题在这一步就暴露了。
2. 选择算法：LP 默认走单纯形法，也可指定内点法；MIP 进入分支定界主循环；QP 用主动集法。
3. 迭代求解：单纯形滑顶点，内点法沿路径逼近，MIP 在每个节点上解一次松弛 LP。
4. 输出结果：模型状态（kOptimal / kInfeasible / kTimeout 等）、变量取值、目标值，MIP 还会报告上下界差距。

🗓️ 端到端案例：用 HiGHS 求解器排 7 天值班表

业务描述很直白：16 名员工要覆盖 7 天、每天早中夜三个班次；工作日每班至少 3/3/2 人，周末加班到 5/5/3 人；每人每周最多干 4 天，同一天不能兼两个班；目标是最小化总人力成本（夜班按 1.5 倍计酬）。

文字建模拆成三件东西：

1. 变量：x[p, d, s]是否让 p 员工第 d 天值 s 班，取值 0 或 1。
2. 约束：每班总人数 ≥ 需求；每人每天至多 1 个班；每人每周至多 4 天。
3. 目标：班次人数乘以班次的成本，求和最小化。

对应代码：

import highspy h = highspy.Highs() h.silent() # 关掉求解器默认日志 P, D, S = 16, 7, 3 # 16 人、7 天、每天 3 班 x = h.addBinaries(P, D, S) # x[p, d, s] 是否为 1 demand = [[3,3,2],[3,3,2],[4,4,2],[4,4,2],[5,5,3],[5,5,3],[4,4,2]] for d in range(D): for s in range(S): h.addConstr(sum(x[p, d, s] for p in range(P)) >= demand[d][s]) for p in range(P): for d in range(D): h.addConstr(x[p,d,0] + x[p,d,1] + x[p,d,2] <= 1) # 一天不兼班 h.addConstr(sum(x[p,d,s] for d in range(D) for s in range(S)) <= 4) h.minimize(sum((1.5 if s == 2 else 1.0) * x[p,d,s] for p in range(P) for d in range(D) for s in range(S))) h.solve() print(h.getModelStatus(), h.getObjectiveValue()) for d in range(D): # 打印 0 号员工的排班 shifts = [s + 1 for s in range(S) if h.vals(x[0, d, s]) > 0.5] print(f"day{d+1}: {shifts}")

怎么解读输出：状态是kOptimal，目标值 64.0。可以手工验证这不是巧合——总需求 56 个班次，其中夜班 16 个，成本下限恰好是 (56-16)×1 + 16×1.5 = 64，说明每个班次都刚好按最低人数排、没有任何"浪费的工时"，而 16 人 × 4 天 = 64 个班次上限也刚好包住需求。打印出来的排班里，0 号员工一周不超过 4 天、每天至多一个班，逐条满足约束。这就是 Python 优化建模的完整闭环：把业务规则翻译成变量、约束、目标，剩下的交给求解器。

把求解时间压下去的几招

1. 预处理默认开启，先别动它。怀疑预处理掩盖了数值问题时，用setOptionValue("presolve", "off")关掉再解一次，对比目标值。
2. 大稀疏 LP 换内点法试试：setOptionValue("solver", "ipm")（或"ipx"）。内点法解完会跑 crossover 得到基解（run_crossover默认 on），跳过它就拿不到基和灵敏度信息。
3. 给 MIP 明确止损信号：time_limit（秒）限总时长；mip_rel_gap默认 0.0001 其实太严，业务场景放到 0.01，往往快一个数量级，解照样能用。
4. 数据量级跨了几个数量级时，先做归一化，或用user_objective_scale/user_bound_scale做 2 的幂缩放。另外注意 HiGHS 会把小于small_matrix_value的系数当 0、大于large_matrix_value的当无穷，数据可能被"静默截断"。
5. 观察性能看getInfo()：单纯形迭代次数、耗时、MIP 节点数都在里面；打开ranging = on还能拿到目标系数和右端项的灵敏度区间，用来回答"这个系数波动多少方案不变"。
6. 全部参数清单在docs/src/options/definitions.md，命令行下--solver、--presolve、--time_limit、--threads等常用项可以直接传。

高频卡点速查：症状、原因、动作

按需进阶：接下来可以看哪

• 如果你要把 HiGHS 嵌进 C/C++ 服务：看highs/interfaces/highs_c_api.h的 C API，以及examples/下的call_highs_from_c.c、call_highs_from_cpp.cpp，是现成的最小调用样例。
• 如果想研究内点法与 GPU 加速的实现：IPX 在highs/ipm/ipx/，HiPO 在highs/ipm/hipo/，并行/分布式求解器在highs/pdlp/，配套测试在check/目录里。
• 如果目标是多目标与灵敏度：examples/multi_objective.py演示了字典序与加权两种多目标写法，ranging选项负责敏感性输出。

动手的三步

HiGHS 求解器的用法可以压缩成一句话：把排班、竞价、路由这类问题写成变量、约束、目标，h.solve()之后从getSolution()和getInfo()里取结果。下一步就打开examples/call_highs_from_python_highspy.py跑一遍，再照着check/里的测试集把自己真实问题的模型写出来——卡住时，测试代码就是最好的参考实现。

【免费下载链接】HiGHSLinear optimization software项目地址: https://gitcode.com/GitHub_Trending/hi/HiGHS