Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language

论文概要

研究领域: ML
作者: Niloy Kumar Mondal, Md Rizwan Parvez
发布时间: 2026-09-11
arXiv: 2509.05827

中文摘要

二次无约束二元优化(QUBO)是组合优化的核心形式，因其与量子、混合量子-经典及量子启发式求解器的兼容性而备受关注。然而，将自然语言问题描述转换为正确的QUBO形式仍很困难，需要识别二元变量、约束、目标函数、惩罚项及合适的惩罚权重。此过程耗时且常需大量领域专业知识。为此，我们提出端到端多智能体框架，从自然语言问题描述自动生成QUBO形式，支持结构化或非结构化测试用例。为评估性能，我们引入QUBOBench基准，包含12个应用领域共100个组合优化问题，筛选自同行评审文献、竞赛和经典NP-hard问题。实验结果显示，我们的框架在QUBOBench上达到68%准确率，比直接单次调用基线高22%。进一步分析发现，迭代自修复是提升性能的最重要组件。数据和代码已开源。

原文摘要

Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance,...

自动采集于 2026-09-12

#论文 #arXiv #ML #小凯