linkedin/DuaLip

# DuaLip：基于对偶分解的线性规划求解器 [](LICENSE) [](https://www.python.org/downloads/) [](https://pytorch.org/) [](https://linkedin.github.io/DuaLip) DuaLip 是一个建立在 PyTorch 基础上的**超大规模线性规划 (LP) 求解器**。它用于求解以下形式的结构化 LP 问题： ``` minimize c^T x subject to Ax ≤ b x_i ∈ C_i for all i ∈ {1, 2, ..., I} ``` 其中 `x = (x_1, ..., x_I)` 是优化变量的完整向量，`x_i` 是与实体 `i`（例如用户）关联的向量，而 `A, b, c, C_i` 是特定于问题的数据。 许多大规模决策系统 —— 如分配、指派、市场 shaping —— 最终都可以归结为定期求解极其庞大的 LP 问题。通用 LP 求解器将约束矩阵视为无结构的算子，无法扩展到这种极端的问题规模。专用的匹配求解器则无法适应生产环境中出现的异构约束族（预算、节奏控制、公平性、频次上限）。 DuaLip 通过一种**岭正则化对偶上升** (ridge-regularized dual ascent) 方法填补了这一空白，该方法： - 利用块对角结构实现大规模并行 - 无需商业求解器许可证 - 完全在配备开源 PyTorch 的商用 GPU 上运行 ## 功能 - **超大规模** —— 支持包含数亿个实体以及多达数万亿变量的结构化 LP - **GPU 加速** —— 通过原生 CUDA 执行，相比之前基于 Spark 的求解器实现了显著的挂钟时间 (wall-clock) 提速 - **以算子为中心的 API** —— 新的 LP 公式只需要一个新的 `ObjectiveFunction`；映射和求解循环均可复用 - **分布式多 GPU** —— 通过 `torch.distributed` (NCCL) 实现横向扩展；通信开销仅取决于对偶维度 - **Nesterov 加速梯度上升** —— 结合基于 Lipschitz 的步长调整、Jacobi 预处理以及可选的 γ 衰减 - **多面体投影** —— 支持盒型、单纯型和锥型约束，可通过注册表模式进行扩展 - **热启动** —— 从之前的对偶解进行初始化，以加快周期性工作负载的收敛速度 - **MLflow 集成** —— 追踪对偶目标、步长、超参数和收敛诊断信息 - **Python 原生** —— 与通用的数值计算和 ML 技术栈保持一致，便于进行插桩 (instrumentation) 和调试 ## 快速入门 ### 环境要求 - Python >= 3.10 - PyTorch >= 2.6.0 ### 安装 ``` pip install -e . ``` ### 用法 ``` import torch from dualip.objectives.matching import MatchingInputArgs from dualip.projections.base import create_projection_map from dualip.run_solver import run_solver from dualip.types import ComputeArgs, ObjectiveArgs, SolverArgs # 构建您的问题数据（CSC 格式中的 A 和 c，预算向量 b） # 以及定义逐列约束的 projection map input_args = MatchingInputArgs( A=A_csc, # sparse constraint matrix (CSC) c=C_csc, # sparse cost matrix (CSC) b_vec=b_vec, # budget / RHS vector projection_map=create_projection_map(projection_entries), ) solver_args = SolverArgs(max_iter=5000, gamma=1e-3) compute_args = ComputeArgs(host_device="cuda:0") objective_args = ObjectiveArgs(objective_type="matching") result = run_solver(input_args, solver_args, compute_args, objective_args) print(f"Dual objective: {result.dual_objective:.6f}") ``` 有关完整的端到端示例，请参见 [examples/movielens_matching/movies_lens_matching.py](examples/movielens_matching/movies_lens_matching.py)，该示例解决了 MovieLens 数据集上的匹配问题。使用 MIPLIB 2017 问题的示例可在 [examples/miplib_2017/](examples/miplib_2017/) 下找到。 有关设置自定义问题的参考，请参见 [benchmark/run_matching_benchmark.py](benchmark/run_matching_benchmark.py)（单 GPU）和 [benchmark/run_matching_benchmark_dist.py](benchmark/run_matching_benchmark_dist.py)（分布式多 GPU）。 ## 基于 PyTorch 的求解器 DuaLip 最初建立在 Scala/Spark 之上。此次 PyTorch 重写是一次从零开始的重构，它用 GPU 原生、可组合的架构取代了以前以 CPU 为中心、受 schema 限制的运行时，在带来显著挂钟时间提速的同时，使得新问题的表达变得极其容易。 该求解器采用了**以算子为中心的编程模型**，该模型围绕三个解耦的原语构建 —— `ObjectiveFunction`、`ProjectionMap` 和 `Maximizer` —— 因此，新的 LP 公式只需要实现一个新的 `ObjectiveFunction`，同时复用求解循环、映射和分布式原语。 **为了提升 GPU 性能的关键设计选择：** - 与块对角结构对齐的稀疏 CSC 存储 - 批处理投影 kernel - 带有 γ 延续策略的 Jacobi 预处理 - 通过 `torch.distributed` (NCCL) 实现分布式多 GPU - 热启动支持 - 纯 PyTorch —— 无需自定义 C++/CUDA kernel ## 文档 完整文档可在 **[linkedin.github.io/DuaLip](https://linkedin.github.io/DuaLip)** 获取。 ## 从基于 Spark 的求解器迁移 这款基于 PyTorch 的求解器是对原版 [Spark/Scala DuaLip 求解器](https://arxiv.org/abs/2103.05277) 的彻底重写。核心的对偶分解算法保持不变，但其实现、数据格式和 API 均为全新设计。 **版本历史：** 标签 `v1.0.0` 到 `v4.0.5` 对应于 Spark/Scala 求解器。PyTorch 的重写版本从 `master` 分支的 `v5.0.1` 开始。 请参阅 [快速入门](#quick-start) 部分和 [examples/movielens_matching/movies_lens_matching.py](examples/movielens_matching/movies_lens_matching.py) 以获取新 API 的示例。 ## 开发 1. **创建并激活虚拟环境** python -m venv .venv && source .venv/bin/activate 2. **安装开发依赖和 pre-commit hooks** make install 3. **运行测试** make test 4. **运行 checkstyle**（格式化 + lint） make checkstyle ## 仓库结构 ``` src/dualip/ Core library objectives/ Objective functions (matching, MIPLIB) optimizers/ Accelerated gradient descent solver projections/ Box, simplex, cone projections preprocessing/ Input validation and Jacobi preconditioning utils/ Sparse, distributed, and MLflow utilities tests/ Unit and distributed tests examples/ Example problems (MovieLens matching, MIPLIB 2017) benchmark/ Scaling and performance benchmarks docs/ Sphinx documentation source ``` ## 引用 DuaLip 如果您在工作中使用了 DuaLip，请引用： ``` @inproceedings{ramanath:21, author = {Ramanath, Rohan and Keerthi, Sathiya S. and Basu, Kinjal and Salomatin, Konstantin and Yao, Pan}, title = {Efficient Algorithms for Global Inference in Internet Marketplaces}, journal = {arXiv preprint arXiv:2103.05277}, year = {2021}, url = {https://arxiv.org/abs/2103.05277} } @InProceedings{pmlr-v119-basu20a, title = {{ECLIPSE}: An Extreme-Scale Linear Program Solver for Web-Applications}, author = {Basu, Kinjal and Ghoting, Amol and Mazumder, Rahul and Pan, Yao}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {704--714}, year = {2020}, volume = {119}, series = {Proceedings of Machine Learning Research}, publisher = {PMLR}, url = {http://proceedings.mlr.press/v119/basu20a.html} } ``` ## 致谢 DuaLip 由 LinkedIn 的 AI Algorithms 团队构建和维护： - [Gregory Dexter](https://www.linkedin.com/in/gregorydexter1/) - [Aida Rahmattalabi](https://www.linkedin.com/in/aida-rahmattalabi-23a4ab4a/) - [Sanjana Garg](https://www.linkedin.com/in/sanjana-garg/) - [Qingquan Song](https://www.linkedin.com/in/qingquan-song-b71167119/) - [Zhipeng Wang](https://www.linkedin.com/in/zhipeng-wang-phd-66806816/) ## 许可证 BSD 2-Clause 许可证。详情请参阅 [LICENSE](LICENSE)。

标签：PyTorch, Vectored Exception Handling, 凭据扫描, 分布式计算, 大规模计算, 对偶分解, 异常处理, 数学优化求解器, 线性规划, 逆向工具