用GPU加速的通用优化框架，30秒解出442城市旅行商问题，精度达95.27%
cuGenOpt: A GPU-Accelerated General-Purpose Metaheuristic Framework for Combinatorial Optimization
- 基于CUDA的单块处理单解架构，支持多种编码格式统一抽象
- 在三类GPU上实现比通用求解器快数个数量级，TSP-442 30秒误差仅4.73%
- 提供纯Python接口和大模型辅助建模，让非专家也能快速调用
组合优化问题广泛存在于物流、调度与资源分配中，现有方法在通用性、性能与易用性间存在根本权衡。本文提出cuGenOpt，一个面向组合优化的GPU加速通用元启发式框架，同时突破三大瓶颈。在引擎层面，采用“一区块演化一解”的CUDA架构，融合统一编码抽象（排列、二进制、整数）、两级自适应算子选择机制与硬件感知资源管理；在可扩展层面，通过用户自定义算子注册接口，支持领域专家注入专用CUDA搜索算子；在易用层面，借助即时编译管线提供纯Python API，并集成大模型驱动的建模助手，将自然语言问题描述转化为可执行求解代码。在三类GPU（T4、V100、A800）上对五组主题实例测试表明，cuGenOpt相比通用混合整数规划求解器提速数个数量级，在规模达n=150的实例上达到与专用求解器相当的解质量，于TSP-442上30秒内实现4.73%差距；共12类问题类型、5种编码变体被求解至最优。框架级优化使pcb442差距从36%降至4.73%，且VRPTW吞吐量提升75%-81%。
原文摘要 · Abstract (English)
Combinatorial optimization problems arise in logistics, scheduling, and resource allocation, yet existing approaches face a fundamental trade-off among generality, performance, and usability. We present cuGenOpt, a GPU-accelerated general-purpose metaheuristic framework that addresses all three dimensions simultaneously. At the engine level, cuGenOpt adopts a "one block evolves one solution" CUDA architecture with a unified encoding abstraction (permutation, binary, integer), a two-level adaptive operator selection mechanism, and hardware-aware resource management. At the extensibility level, a user-defined operator registration interface allows domain experts to inject problem-specific CUDA search operators. At the usability level, a JIT compilation pipeline exposes the framework as a pure-Python API, and an LLM-based modeling assistant converts natural-language problem descriptions into executable solver code. Experiments across five thematic suites on three GPU architectures (T4, V100, A800) show that cuGenOpt outperforms general MIP solvers by orders of magnitude, achieves competitive quality against specialized solvers on instances up to n=150, and attains 4.73% gap on TSP-442 within 30s. Twelve problem types spanning five encoding variants are solved to optimality. Framework-level optimizations cumulatively reduce pcb442 gap from 36% to 4.73% and boost VRPTW throughput by 75-81%. Code: https://github.com/L-yang-yang/cugenopt
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。