NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912059972648960 |
|---|---|
| author | Xiong, Zhixiao Zong, Fangyu Ye, Huigen Xu, Hua |
| author_facet | Xiong, Zhixiao Zong, Fangyu Ye, Huigen Xu, Hua |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03720 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs Xiong, Zhixiao Zong, Fangyu Ye, Huigen Xu, Hua Optimization and Control Machine Learning 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. |
| title | NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2410.03720 |