[论文] Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulat...

论文概要

研究领域: cs.AI
作者: Niloy Kumar Mondal, Md Rizwan Parvez
发布时间: 2026-09-13
arXiv: 2609.10629

中文摘要

二次无约束二进制优化（QUBO）是组合优化的核心形式，由于与量子、混合量子经典和量子启发式求解器的兼容性而日益受到关注。然而，将自然语言问题描述转换为正确的 QUBO 形式仍然困难，需要识别二进制变量、约束、目标函数、惩罚项和合适的惩罚权重。这个过程耗时且通常需要大量领域专业知识。为解决这一挑战，我们提出端到端的多智能体框架，自动从自然语言问题描述生成 QUBO 形式，支持结构化或非结构化测试用例。我们还引入 QUBOBench 基准，包含 12 个应用领域的 100 个组合优化问题。实验结果显示，我们的框架在 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, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at this https URL.

自动采集于 2026-09-13

#论文 #arXiv #AI #小凯