#moonopt

• 模型输入：MPS（free / fixed）、CPLEX LP
• 线性求解：稀疏 CSC + 稀疏 LU 基分解的修正单纯形，增益定价，Harris 两遍比值检验，有界变量枢轴， 对偶单纯形热启动，presolve / postsolve
• 整数求解：best-bound 分支定界，节点热启动，根割（混合整数舍入，附推导证明）， 取整 / 下潜 / 可行性泵三种原始启发式，0/1 集覆盖模型上的列支配归约（默认开，精确变换）
• 证书：最优性、Farkas 不可行性、无界射线，可序列化为 JSON；verify 包独立复核，不依赖 simplex
• 目标平台：native / wasm / wasm-gc / js

#安装

moon add Freon793/moonopt

#快速开始

/// max 5x + 4y  s.t.  6x + 4y <= 24,  x + 2y <= 6,  x, y >= 0   ->  21 at (3, 1.5)
fn demo() -> Unit {
  let m = @model.Model::new(@model.Sense::Maximize)
  let x = m.add_var("x")
  let y = m.add_var("y")
  m.set_objective([(x, 5.0), (y, 4.0)])
  m.add_named_constraint([(x, 6.0), (y, 4.0)], @model.Rel::LessEqual, 24.0, "machine_hours")
  m.add_named_constraint([(x, 1.0), (y, 2.0)], @model.Rel::LessEqual, 6.0, "labour_hours")
  let sol = @moonopt.solve(m)
  match sol.status {
    @moonopt.SolveStatus::Optimal => println("objective = " + sol.objective.to_string())
    _ => println("not solved: " + sol.message)
  }
}

moon run examples/production_plan    # 两产品生产计划（最优 21 at (3, 1.5)）
moon run examples/transportation     # 产销平衡运输问题（全等式约束，走 Phase I；最优 11）
moon run examples/schedule_bound     # 手上已有一份排班表时它值多少：LP 界 7.5、最优 11、这份方案 12
moon run cmd/main                    # 打印示例模型与一个"当前不支持"的诚实案例

#命令行

moon run cmd/parse -- <file.mps>                                # 巡检：格式、规模、校验结论
moon run cmd/parse -- solve <file.mps> --relax --presolve        # 线性求解（默认走 presolve）
moon run cmd/parse -- solve <file.mps> --mip --max-nodes 2000    # 分支定界，每个松弛过 verify
moon run cmd/parse -- verify <file.mps> --relax                  # 求解并用独立校验器复核证书
moon run cmd/parse -- verify <file.mps> --certificate cert.json  # 只校验证书，不重解
moon run cmd/parse -- fmt <file.mps> --format lp -o out.lp       # 读→写
moon run cmd/parse -- bench --manifest instances.txt --mip --max-nodes 300

#支持的模型

#什么时候它不是合适的选择

• 规模：内核行数上限 200 000（稀疏 LU，内存 O(nnz + fill)），超过就返回 TooLarge。清单里 3 个实例抬到 --max-rows 20000 仍解不完——core2536-691 与 dano3_3 卡在 Phase I 的枢轴成本、 2club200v15p5scn 是 17 013 行的规模本身；mod011 是在等式 doubleton 代入把它降到 2 402 行之后 才解出来的。"几千行 + 系数跨若干数量级"这一带，先假设它会失败。
• 高度退化的实例：fast0507（507 条覆盖行、63 009 个 0/1 变量）20 000 个枢轴没有收敛，60 000 到 139.78、150 000 到 133.18 —— 还在降，但每千枢轴的增益已从 0.61 掉到 0.073。
• 整数规划要的是"证明"：宽口径（32 个实例、600 个节点）证到 5 个最优，小规模（10 个、30 000 个 节点）证到 6 个；其余返回 node-limit 并带上当前解与开界——那是诚实的答案，不是最优性证明。 界本身就贴 LP 松弛的那一类，加预算也推不动（noswot 从 30 000 翻到 60 000 个节点，界一动没动）。
• 想靠割平面抬界：只有单行的混合整数舍入割，且只在根节点做。选择规则（五条）、割族（多行 MIR 聚合、二值 cover、覆盖型 cover、flow cover 的结构前提）、节点割都已实测并关闭。反过来， markshare1 / markshare2 是纯等式模型（没有 ≤/≥ 行对）、noswot 的"需求行"其实是 job-shop 的时序约束——这两类的界不会被覆盖类割抬高，换哪一族都一样。
• 需要证书被外部工具读：证书是 JSON，但只对内核收到的模型成立（校验路径不化简），化简模型的 乘子不会回映到原模型；换成有理数证书（例如 VIPR）需要另一套算术子系统，本项目没做。
• 需要一个整数可行点、而松弛点本身是分数：整数无界性的证明要求"点与改善射线在整数变量上都取整数"， 点本身分数时只报 UnboundedRelaxation（松弛无界、模型未知），找可行点仍归搜索。
• 以下功能不在计划里：非线性 / 半定规划、并行、网络单纯形专用路径、Python / JS 绑定、MPS 的 SC / SI 半连续界与完整 SOS / MARKER 语义、行 / 列的支配检测、精确 steepest-edge 定价。

#真实数据与基准

powershell -NoProfile -ExecutionPolicy Bypass -File bench/fetch-instances.ps1   # 下载实例
powershell -NoProfile -ExecutionPolicy Bypass -File bench/report.ps1            # 四份报告是否仍被当前代码支持

#项目结构

moonopt.mbt       公开入口：solve / solve_with、SolveStatus、Solution、SolveOptions
core/             数值与稀疏基础设施（容差比较、补偿求和、CSC 稀疏矩阵）
model/            模型层（变量、线性表达式、约束、目标、模型校验）
format/           MPS 与 LP 读写、解析错误定位
oracle/           参考实现：稠密两阶段单纯形（差分测试的对照基准，不是交付求解器）
simplex/          稀疏修正单纯形内核、稀疏 LU、对偶单纯形热启动、证书生产端自检
presolve/         模型化简与解还原
verify/           独立校验器：最优性、Farkas、无界射线、割的再推导（不依赖 simplex）
mip/              分支定界、根割、原始启发式
cmd/main/         演示 CLI        cmd/parse/  模型巡检与求解 CLI
examples/         可运行示例      bench/      数据政策、下载与报告脚本、报告
docs/             设计、算法、API 契约、路线图、生态调研、验收对照

#文档

#开发

moon check --deny-warn
moon test --deny-warn
moon fmt && git diff --exit-code
moon info && git diff --exit-code   # .mbti 是接口合同，必须随代码提交

#许可与数据

• 本项目以 Apache-2.0 发布，见 LICENSE。
• 算法实现基于公开文献，代码为本项目原创，未移植任何第三方实现。
• 基准实例（MIPLIB 2017）是第三方数据，不由本仓库再分发：仓库里只有下载脚本与本项目自己写的清单， .moonignore 保证它们不进发布归档。细节见 bench/README.md。