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.
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.
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.
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.
Many complex problems encountered in both production and daily life can be conceptualized as combinatorial optimization problems (COPs). Many ad-hoc deep learning methods have been proposed to solve these problems, but there still lacks an effective unified framework. In this work, we take a step towards this goal by designing an unified end-to-end deep reinforcement learning framework named CONQUER. CONQUER first translates various COPs into the unified QUBO (Quadratic Unconstrained Binary Optimization) formalization, and afterwards trains a neural QUBO solver to search high-quality strategies, which are then checked and repaired to obtain the solutions for original COPs. The QUBO solver is a purely data-driven neural model, which does not rely on any expert inputs. We adopt the graph transformer network to represent the QUBO graph, so as to effectively capture the features of problem objective and constraints. The Deep Q-network is utilized to train the QUBO solver to find long-sighted solution strategies. Despite being trained solely on small synthetic graphs, CONQUER exhibits promising generality on much larger instances, and can be easily adapted to real-world datasets. Experimentally, we show that CONQUER achieves the state-of-the-art performances on four COPs over graphs, including minimum vertex cover, maximum independent set, maximum clique and maximum cut problem.
Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.
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.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.