Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Neural Computing and Applications

Method for solving constrained 0-1 quadratic programming problems based on pointer network and reinforcement learning

Shenshen Gu, Yuxi Zhuang

Published Jul 30, 2022• 3 citations
Publisher
DOI
10.1007/s00521-022-07604-8

Related papers

A pointer network based deep learning algorithm for unconstrained binary quadratic programming problem

Shenshen Gu, Tao Hao, Hanmei Yao

Neurocomputing•Mar 10, 2020•29 citations

On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks

Chenyang Wu, Qian Chen, Akang Wang +4 more

Convex quadratically constrained quadratic programs (QCQPs) involve finding a solution within a convex feasible region defined by quadratic constraints while minimizing a convex quadratic objective function. These problems arise in various industrial applications, including power systems and signal processing. Traditional methods for solving convex QCQPs primarily rely on matrix factorization, which quickly becomes computationally prohibitive as the problem size increases. Recently, graph neural networks (GNNs) have gained attention for their potential in representing and solving various optimization problems such as linear programs and linearly constrained quadratic programs. In this work, we investigate the representation power of GNNs in the context of QCQP tasks. Specifically, we propose a new tripartite graph representation for general convex QCQPs and properly associate it with message-passing GNNs. We demonstrate that there exist GNNs capable of reliably representing key properties of convex QCQPs, including feasibility, optimal value, and optimal solution. Our result deepens the understanding of the connection between QCQPs and GNNs, paving the way for future machine learning approaches to efficiently solve QCQPs.

arXiv:2411.13805•Nov 21, 2024•0 citations

Heuristic algorithms based on deep reinforcement learning for quadratic unconstrained binary optimization

Ming Chen, Yuning Chen, Yonghao Du +2 more

Knowledge-Based Systems•Aug 8, 2020•18 citations

Comparing quantum hybrid reinforcement learning to classical methods

Maximilian Moll, Leonhard Kunczik

Abstract In recent history, reinforcement learning (RL) proved its capability by solving complex decision problems by mastering several games. Increased computational power and the advances in approximation with neural networks (NN) paved the path to RL’s successful applications. Even though RL can tackle more complex problems nowadays, it still relies on computational power and runtime. Quantum computing promises to solve these issues by its capability to encode information and the potential quadratic speedup in runtime. We compare tabular Q-learning and Q-learning using either a quantum or a classical approximation architecture on the frozen lake problem. Furthermore, the three algorithms are analyzed in terms of iterations until convergence to the optimal behavior, memory usage, and runtime. Within the paper, NNs are utilized for approximation in the classical domain, while in the quantum domain variational quantum circuits, as a quantum hybrid approximation method, have been used. Our simulations show that a quantum approximator is beneficial in terms of memory usage and provides a better sample complexity than NNs; however, it still lacks the computational speed to be competitive.

Human-Intelligent Systems Integration•Mar 1, 2021•12 citations

Quadratic convex reformulations for quadratic 0–1 programming

Marie-Christine Plateau

4OR•May 29, 2007•4 citations

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

Zhixiao Xiong, Huigen Ye, Hua Xu +1 more

Machine learning-based optimization frameworks have attracted increasing attention for accelerating the solution of large-scale quadratically constrained quadratic programs (QCQPs) by exploiting shared problem structure across instances. However, existing machine learning (ML) frameworks often rely on the assumption of parametric models and large-scale solvers. This article introduces HEQP, a hypergraph neural network-based evolutionary optimization framework for large-scale QCQPs. This framework features two main components: 1) hypergraph-based neural prediction, which predicts optimal solutions for QCQPs without assumptions of models; and 2) evolutionary large neighborhood search (Evo-LNS), which employs a McCormick relaxation-based repair strategy to search and apply crossover on neighborhood solutions using a small-scale solver. We further show that our framework is equivalent to the interior-point method (IPM), a polynomial-time algorithm, for quadratic programming. Experiments on two types of benchmark problems and 13 large-scale real-world instances from the QPLIB illustrate that our framework outperforms state-of-the-art solvers (including Gurobi, SCIP, and SHOT) in both solution quality and time efficiency, highlighting the efficiency of ML-based optimization frameworks for QCQPs.

IEEE Transactions on Cybernetics•Feb 6, 2026•0 citations
Convex quadratically constrained quadratic programs (QCQPs) involve finding a solution within a convex feasible region defined by quadratic constraints while minimizing a convex quadratic objective function. These problems arise in various industrial applications, including power systems and signal processing. Traditional methods for solving convex QCQPs primarily rely on matrix factorization, which quickly becomes computationally prohibitive as the problem size increases. Recently, graph neural networks (GNNs) have gained attention for their potential in representing and solving various optimization problems such as linear programs and linearly constrained quadratic programs. In this work, we investigate the representation power of GNNs in the context of QCQP tasks. Specifically, we propose a new tripartite graph representation for general convex QCQPs and properly associate it with message-passing GNNs. We demonstrate that there exist GNNs capable of reliably representing key properties of convex QCQPs, including feasibility, optimal value, and optimal solution. Our result deepens the understanding of the connection between QCQPs and GNNs, paving the way for future machine learning approaches to efficiently solve QCQPs.
Abstract In recent history, reinforcement learning (RL) proved its capability by solving complex decision problems by mastering several games. Increased computational power and the advances in approximation with neural networks (NN) paved the path to RL’s successful applications. Even though RL can tackle more complex problems nowadays, it still relies on computational power and runtime. Quantum computing promises to solve these issues by its capability to encode information and the potential quadratic speedup in runtime. We compare tabular Q-learning and Q-learning using either a quantum or a classical approximation architecture on the frozen lake problem. Furthermore, the three algorithms are analyzed in terms of iterations until convergence to the optimal behavior, memory usage, and runtime. Within the paper, NNs are utilized for approximation in the classical domain, while in the quantum domain variational quantum circuits, as a quantum hybrid approximation method, have been used. Our simulations show that a quantum approximator is beneficial in terms of memory usage and provides a better sample complexity than NNs; however, it still lacks the computational speed to be competitive.
Machine learning-based optimization frameworks have attracted increasing attention for accelerating the solution of large-scale quadratically constrained quadratic programs (QCQPs) by exploiting shared problem structure across instances. However, existing machine learning (ML) frameworks often rely on the assumption of parametric models and large-scale solvers. This article introduces HEQP, a hypergraph neural network-based evolutionary optimization framework for large-scale QCQPs. This framework features two main components: 1) hypergraph-based neural prediction, which predicts optimal solutions for QCQPs without assumptions of models; and 2) evolutionary large neighborhood search (Evo-LNS), which employs a McCormick relaxation-based repair strategy to search and apply crossover on neighborhood solutions using a small-scale solver. We further show that our framework is equivalent to the interior-point method (IPM), a polynomial-time algorithm, for quadratic programming. Experiments on two types of benchmark problems and 13 large-scale real-world instances from the QPLIB illustrate that our framework outperforms state-of-the-art solvers (including Gurobi, SCIP, and SHOT) in both solution quality and time efficiency, highlighting the efficiency of ML-based optimization frameworks for QCQPs.