While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits.
While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits.
This paper investigates the application of quantum annealing in conjunction with graph neural networks (GNNs) for solving complex combinatorial optimization problems. Traditional classical optimization algorithms often face significant challenges in identifying optimal solutions within large and intricate solution spaces. The core idea presented herein is to represent these problems as graphs and utilize the inherent quantum mechanical properties of quantum annealing to explore this space more efficiently. Specifically, GNNs are employed to generate embeddings of the graph, effectively encoding problem-specific features and relationships. This approach aims to bridge the gap between the probabilistic nature of quantum computation and the structural information captured by GNNs. We detail the theoretical framework, explore the potential benefits of this hybrid approach, and outline a methodology for integrating these techniques. The potential for improved optimization performance compared to conventional methods is discussed, highlighting the synergy between quantum annealing's ability to find low-energy states and GNNs' capacity to learn complex graph representations.
In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these methods is to represent a CO problem as a graph and then use GNNs to learn the node/graph embedding with combinatorial information. Although these methods have achieved promising results, given a specific CO problem, the design of GNN architectures still requires heavy manual work with domain knowledge. Existing automated GNNs are mostly focused on traditional graph learning problems, which is inapplicable to solving NP-hard CO problems. To this end, we present a new class of \textbf{AUTO}mated \textbf{G}NNs for solving \textbf{NP}-hard problems, namely \textbf{AutoGNP}. We represent CO problems by GNNs and focus on two specific problems, i.e., mixed integer linear programming and quadratic unconstrained binary optimization. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard combinatorial optimization problem. Compared with existing graph neural architecture search algorithms, AutoGNP utilizes two-hop operators in the architecture search space. Moreover, AutoGNP utilizes simulated annealing and a strict early stopping policy to avoid local optimal solutions. Empirical results on benchmark combinatorial problems demonstrate the superiority of our proposed model.
Integer Programming (IP) constitutes a formidable framework for modeling and solving a vast array of real-world combinatorial optimization problems. However, the NP-hard nature of IPs often renders exact solutions computationally intractable for large-scale instances. Concurrently, deep learning (DL) has demonstrated unprecedented success in learning complex patterns and making data-driven predictions across various domains. This paper explores a novel paradigm for unifying these two powerful methodologies by leveraging graph representations. We propose a framework where IP problems are first translated into a rich graph structure, capturing variables, constraints, and their interdependencies. Graph Neural Networks (GNNs) are then employed to learn intricate features from these graph representations, which can subsequently inform or augment traditional IP solvers. Specifically, we investigate how GNNs can predict effective branching decisions, generate cutting planes, or guide primal heuristics, thereby accelerating the search for optimal or near-optimal integer solutions. This unification aims to transcend the limitations of purely heuristic approaches by grounding DL predictions within the rigorous mathematical framework of IP, while simultaneously injecting learning-based intelligence into the traditionally exact yet computationally intensive optimization process. Our approach seeks to develop hybrid algorithms that combine the generalization capabilities of deep learning with the guarantee-seeking nature of integer programming, potentially leading to significant advancements in solving complex optimization challenges.
Recent advances in deep learning techniques pose a question of whether they can facilitate the task of finding good quality solutions to combinatorial optimization (CO) problems in a practically relevant solution time. Specifically, it is of practical relevance to determine to which extent graph neural networks (GNNs) can be applied to CO problems that can be formulated as QUBO’s and thus be naturally interpreted as graph problems. In this research a GNNsolver is applied to two classical CO problems–the maximum cut problem and maximum independent set problem–in an unsupervised learning setting. We show that while GNN solver consistently finds good quality solutions for the Max Cut problem irrespective of the size and density of the graph, solving MIS problems is challenging for all but very sparse graphs. We further show how this problem can be addressed by embedding transfer between these two problems and compare two different GNN architectures–GCN and GraphSAGE on their robustness with respect to graph density and symmetry. Finally we demonstrate that change of widely used Adam optimizer to Rprop optimizer can lead to considerable reduction of solution times. • Previously suggested GNNsolver is effective on sparse graphs only. • Replacing Adam with RPROP reduced solution times. • GraphSAGE can handle denser graphs, GCN performs better on sparse graphs. • Transfer learning between MaxCut and MIS problems improves solvers performance.
In recent years, the advantages of Graph Neural Networks (GNNs) in solving complex combinatorial optimization problems have become more and more obvious. Under this background, this paper demonstrates a method based on GNNs to solve large-scale Unconstrained 0–1 Quadratic Programming (UBQP) problems. Firstly, the UBQP problem models of different combinatorial optimization problems are converted into a unified graph model. This approach makes up for the shortcoming that GNNs cannot be effectively applied to combinatorial optimization problems not based on graph. Secondly, based on Graph Attention Network (GAT) algorithm, this study designs a general GNN model capable of solving UBQP problems. In addition, a random sampling scheme for the complete graph structure is devised, which greatly alleviates the pronounced over-smoothing phenomenon when the model is applied to complete graphs and speeds up the convergence rate. In this paper, a supervised learning approach is adopted to train and test a unified structured model (without changing network parameters) on UBQP problems of varying sizes, and to evaluate the model's generalization ability on high-dimensional UBQP problems. Furthermore, an unsupervised learning mechanism is utilized to train and solve individual sample problems of different dimensions. These experimental results consistently demonstrate that the model and strategy presented in this paper exhibit strong solving ability and generalization ability for combinatorial optimization problems.
In recent years, there has been notable interest in investigating combinatorial optimization (CO) problems by neural-based framework. An emerging strategy to tackle these challenging problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms, a subject that has attracted considerable attention. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. The primary focus of our work is to formulate a more efficient and precise framework for CO by employing decision-focused learning on graphs. Additionally, we introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support. To realize an end-to-end approach, we have designed two cascaded modules: (a) an unsupervised trained graph predictive model, and (b) a solver for quadratic binary unconstrained optimization. Empirical evaluations are conducted on various classical tasks, including maximum cut, maximum independent set, and minimum vertex cover. The experimental results on classical CO problems (i.e. MaxCut, MIS, and MVC) demonstrate the superiority of our method over both the standalone GNN approach and classical methods.