HEQP: A Hypergraph Neural Network-Based Evolutionary Method for Large-Scale QCQPs.

Area of Science:

• Optimization
• Machine Learning
• Computational Mathematics

Background:

• Machine learning (ML) frameworks accelerate large-scale quadratically constrained quadratic programs (QCQPs) by leveraging shared structures.
• Existing ML frameworks often require parametric models and large-scale solvers, limiting their applicability.
• There is a need for ML-based optimization frameworks that overcome these limitations for QCQPs.

Purpose of the Study:

• Introduce HEQP, a hypergraph neural network-based evolutionary optimization framework for large-scale QCQPs.
• Address the limitations of existing ML frameworks by removing assumptions of parametric models and large-scale solvers.
• Demonstrate the effectiveness of HEQP in solving QCQPs efficiently and with high solution quality.

Main Methods:

• HEQP utilizes hypergraph-based neural prediction to forecast optimal QCQP solutions without model assumptions.
• It incorporates evolutionary large neighborhood search (Evo-LNS) with a McCormick relaxation-based repair strategy.
• A small-scale solver is employed for neighborhood solution crossover, enhancing the search process.

Main Results:

• HEQP demonstrates equivalence to the interior-point method (IPM), a polynomial-time algorithm for quadratic programming.
• Experiments on benchmark and real-world QPLIB instances show HEQP outperforms state-of-the-art solvers like Gurobi, SCIP, and SHOT.
• The framework achieves superior solution quality and time efficiency compared to existing methods.

Conclusions:

• HEQP offers an efficient ML-based optimization framework for large-scale QCQPs.
• The framework successfully overcomes limitations of traditional ML approaches in optimization.
• HEQP highlights the potential of ML-driven strategies for advancing computational optimization.