Show HN: 在浏览器中利用 Google OR-Tools 解决复杂优化问题

背景

组合优化问题（Combinatorial Optimization）广泛存在于物流调度、资源分配、生产计划等场景中。Google 推出的开源工具包 Google OR-Tools 是解决此类问题的行业标准库之一，支持约束规划（CP-SAT）、线性规划、路由优化等多种算法。然而，OR-Tools 传统上主要运行在服务器端或本地环境中，依赖 C++ 后端，难以直接应用于需要低延迟、高隐私保护或离线运行的 Web 端场景。

随着 WebAssembly (Wasm) 技术的成熟，将高性能计算库移植到浏览器成为可能。本项目 or-tools-wasm 正是这一趋势下的产物，它通过 Emscripten 将 Google OR-Tools 编译为 WebAssembly，并封装为 TypeScript 库，使得开发者能够在浏览器端直接运行多线程的优化求解器。该项目已在 PragmaPlanner 等实际产品中得到应用，旨在填补前端复杂计算能力的空白。

核心内容

1. 项目概述与技术栈

该项目提供了一个 npm 包 or-tools-wasm，允许开发者使用 TypeScript 编写复杂的优化模型，并在浏览器中通过多线程 WebAssembly 运行求解器。它保留了 OR-Tools 的核心算法能力，同时适配了 Web 环境的特性。

2. API 设计与使用方式

TypeScript API 的设计尽量映射了原生 OR-Tools 的公共 API 结构，确保熟悉 OR-Tools 的开发者能快速上手。主要支持的求解器模块包括：

• CP-SAT: 提供类似 Python 的高级构建器以及基于 Protobuf 的 CpSat API。
• Routing: 暴露熟悉的 RoutingIndexManager 和 RoutingModel API。
• MPSolver: 提供类似 pywraplp 风格的求解器 API。
• MathOpt: 提供 TypeScript 模型构建器。
• 其他模块: 包括 PDLP, RCPSP, Knapsack, Network Flow, Set Cover 等。

代码示例： 开发者可以定义模型变量、约束和目标函数，然后通过 CpSat 创建、验证并求解模型。

import { CpSat } from 'or-tools-wasm/cp-sat';

const model = {
  name: 'choose_one',
  variables: [
    { name: 'x', domain: [0, 1] },
    { name: 'y', domain: [0, 1] },
  ],
  constraints: [
    {
      name: 'exactly_one',
      linear: {
        vars: [0, 1],
        coeffs: [1, 1],
        domain: [1, 1],
      },
    },
  ],
  objective: {
    vars: [0, 1],
    coeffs: [1, 2],
  },
};

// 创建模型字节流
const modelBytes = await CpSat.createModel(model);
// 验证模型
const validation = await CpSat.validate(modelBytes);
if (!validation.ok) {
  throw new Error(validation.message);
}
// 执行求解，指定搜索线程数
const result = await CpSat.solve(modelBytes, {
  numSearchWorkers: 1,
});
console.log(result.response);

3. 浏览器环境配置要求

由于 WebAssembly 线程和 SIMD（单指令多数据）特性依赖于 SharedArrayBuffer，浏览器页面必须启用跨域隔离（Cross-Origin Isolation）。否则，浏览器可能会阻止 SharedArrayBuffer，导致求解器在运行时或 Worker 启动时失败。

必须添加以下 HTTP 响应头：

Cross-Origin-Opener-Policy: same-origin
Cross-Origin-Embedder-Policy: require-corp

配置示例（Vite）：

// vite.config.ts
export default defineConfig({
  server: {
    headers: {
      'Cross-Origin-Opener-Policy': 'same-origin',
      'Cross-Origin-Embedder-Policy': 'require-corp',
    },
  },
  preview: {
    headers: {
      'Cross-Origin-Opener-Policy': 'same-origin',
      'Cross-Origin-Embedder-Policy': 'require-corp',
    },
  },
});

4. 多线程与 Worker 桥接

• 主线程保护：浏览器端的求解可以通过隐藏的 Worker 桥接运行，从而避免阻塞主线程，确保 UI 渲染、用户输入和进度显示不受影响。
• Worker 桥接支持：该功能适用于 CP-SAT, Routing, MPSolver, Knapsack, Network Flow, Set Cover, RCPSP, MathOpt 和 PDLP。
• 线程设置：
  • 支持多线程的求解器（如 CP-SAT, SCIP/GSCIP, CBC, RCPSP 等）可以接受求解器线程设置。
  • 单线程求解器（如 GLPK, BOP, Set Cover）虽然不能设置求解器线程数，但仍可通过浏览器 Worker 桥接运行，以释放主线程。
  • Knapsack 和 Network Flow 可通过 Worker 桥接运行，但不暴露求解器线程设置。

5. 运行时环境与兼容性

• 浏览器：自动从包导入中生成 Worker 脚本和 WebAssembly 文件，无需手动复制到 public/ 或 static/ 目录。支持 Vite, Webpack, Rollup, Deno, Node, Bun 等构建工具。
• Node.js / Bun / Deno：
  • 使用正常的 ESM 导入，不需要浏览器的跨域隔离头。
  • 运行时选择：如果 WebAssembly.promising (JSPI) 可用，则使用 JSPI 运行时；否则回退到 Asyncify 运行时。
  • Deno 权限：需要 --allow-read 和 --allow-sys=cpus 权限来读取包资产和检查 CPU 数量。
• 构建工具：Emscripten SDK 作为 git submodule 跟踪，构建脚本会自动初始化。

6. 测试与基准测试

• 提供完整的测试矩阵，涵盖不同构建工具（Vite, Webpack, Rollup）、运行时（Deno, Node, Bun）以及浏览器环境（Chromium, Firefox, 直接运行时, Worker 桥接）。
• 命令 npm run test:fixtures 运行所有用例。
• 命令 npm run test:fixtures:browser 用于聚焦浏览器环境的迭代测试。

7. 限制与未来规划

• 未暴露的目标：部分 OR-Tools 目标尚未通过此包暴露（标记为 unchecked rows）。
• 商业后端：不计划支持 Gurobi, CPLEX, XPRESS, HiGHS, OSQP, ECOS, SCS 等商业或大型第三方原生后端。
• 许可证：上游项目 Google OR-Tools 采用 Apache License 2.0，本项目同样采用 Apache License 2.0。

关键要点

• 前端优化能力突破：首次将 Google OR-Tools 的核心求解能力（如 CP-SAT, Routing）完整移植到浏览器端，支持多线程 WebAssembly 执行。
• 无缝集成：提供 TypeScript 接口，API 设计与原生 OR-Tools 高度一致，降低了学习成本。
• 性能与体验平衡：通过 Worker 桥接机制，确保求解过程不阻塞主线程，维持 Web 应用的响应性。
• 环境依赖严格：浏览器端运行必须配置 Cross-Origin-Opener-Policy 和 Cross-Origin-Embedder-Policy 响应头以启用 SharedArrayBuffer。
• 多环境支持：不仅支持浏览器，还兼容 Node.js, Deno, Bun 等运行时，并根据环境自动选择 JSPI 或 Asyncify 运行时。
• 开源与许可：基于 Apache License 2.0，上游依赖 Google OR-Tools，