用超图神经网络加速大规模二次约束二次规划求解
NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs
- 基于超图建模问题结构，无需强假设直接预测解
- 通过麦考伊克松弛修复非法变量，迭代提升解质量
- 实测比Gurobi、SCIP更快更准，适合工业级优化场景
机器学习优化框架通过学习共享问题结构，可加速大规模二次约束二次规划（QCQPs）的求解。然而现有方法常依赖强假设并依赖大规模求解器。本文提出NeuralQP，一种通用的超图基框架，包含两个核心组件：超图神经预测模块，可在无问题假设下生成嵌入与预测解；并行邻域优化模块，基于麦考伊克松弛的修复策略识别并修正非法变量，利用小规模求解器迭代改进解。我们进一步证明，所提出的UniEGNN结合超图表示等价于二次规划的内点法（IPM）。在两个基准问题及来自QPLIB的大规模真实实例上，NeuralQP在解质量与时间效率上均优于现有先进求解器（如Gurobi和SCIP），验证了机器学习优化框架在QCQPs中的高效性。
原文摘要 · Abstract (English)
Machine Learning (ML) optimization frameworks have gained attention for their ability to accelerate the optimization of large-scale Quadratically Constrained Quadratic Programs (QCQPs) by learning shared problem structures. However, existing ML frameworks often rely heavily on strong problem assumptions and large-scale solvers. This paper introduces NeuralQP, a general hypergraph-based framework for large-scale QCQPs. NeuralQP features two main components: Hypergraph-based Neural Prediction, which generates embeddings and predicted solutions for QCQPs without problem assumptions, and Parallel Neighborhood Optimization, which employs a McCormick relaxation-based repair strategy to identify and correct illegal variables, iteratively improving the solution with a small-scale solver. We further prove that our framework UniEGNN with our hypergraph representation is equivalent to the Interior-Point Method (IPM) for quadratic programming. Experiments on two benchmark problems and large-scale real-world instances from QPLIB demonstrate that NeuralQP outperforms state-of-the-art solvers (e.g., Gurobi and SCIP) in both solution quality and time efficiency, further validating the efficiency of ML optimization frameworks for QCQPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。