Combinatorial Optimization and Reasoning with Graph Neural Networks

Quentin CappartDidier ChételatElias B. KhalilAndrea LodiChristopher MorrisPetar Velickovic

article2023JMLR526 citations

Synthesizes recent advancements at the intersection of machine learning and operations research, providing a unified framework for how graph neural networks can act as standalone solvers or integrate into classical exact algorithms to solve hard combinatorial problems efficiently.

Listen

Combinatorial optimization addresses critical resource-allocation, routing, and scheduling problems across industries. While these problems are typically non-convex, discrete, and theoretically intractable in the worst case, real-world instances often stem from recurring patterns within specific problem distributions. Historically, exact solvers, heuristics, and approximation algorithms treated each instance in isolation, relying on intensive manual engineering. Recently, machine learning—specifically Graph Neural Networks (GNNs)—has emerged as a promising approach to capture these underlying data distributions, exploit problem symmetries, and respect graph sparsity.

The article provides a comprehensive conceptual review evaluating the integration of GNNs into combinatorial optimization. It analyzes how GNNs serve as standalone heuristic solvers, assist classical exact solvers, and enable end-to-end algorithmic reasoning directly on raw, real-world data.

The authors assess the field by synthesizing empirical and theoretical literature across major optimization paradigms, including Mixed-Integer Linear Programming, Boolean Satisfiability (SAT), and Constraint Programming. They categorize applications into primal approaches for generating feasible solutions, dual approaches for proving optimality bounds, and neural algorithmic reasoning architectures designed to emulate standard computational procedures.

The analysis yields five key findings. First, on the primal side, GNNs trained via supervised, unsupervised, or reinforcement learning can quickly construct solutions for problems like the Traveling Salesperson Problem and Max-Cut; however, enforcing strict combinatorial constraints remains difficult without hybrid search decoders. Second, on the dual side, integrating GNNs within exact solvers—specifically to imitate computationally expensive variable selection (strong branching) or cutting-plane selection—consistently speeds up Mixed-Integer Programming and SAT solvers. Third, algorithmic alignment theory demonstrates that GNN architectures structured to match dynamic programming components (such as using element-wise maximum aggregation for shortest-path routines) generalize significantly better to larger, out-of-distribution instances. Fourth, the encode-process-decode blueprint allows pre-trained neural algorithmic processors to operate on rich, natural inputs directly, bypassing error-prone manual feature abstraction. Finally, standalone GNN performance remains substantially inferior to highly engineered classical solvers; for instance, standard heuristics can solve routing problems with millions of nodes, whereas standalone GNNs struggle beyond hundreds of nodes.

These findings indicate that while GNNs are not a direct replacement for classical solvers, they offer substantial value as integrated components within hybrid pipelines. Incorporating learned heuristics reduces solver runtimes, manages complex operational contexts, and limits the need for expensive manual tuning. However, practitioners must weigh the polynomial-time inference overhead of neural networks against the rapid execution of simple, hand-crafted decision rules, especially in high-frequency solver subroutines.

Organizations should focus near-term adoption on hybrid workflows, such as using GNNs to guide branching, cut selection, or warm-start heuristics inside proven solvers, rather than deploying standalone neural optimizers. Further research and piloting are required to establish generic software interfaces, optimize execution speeds to avoid CPU-GPU transfer bottlenecks, and expand algorithmic reasoning architectures to support recursive and complex primitives.

Confidence in hybrid integration is moderate to high based on consistent empirical gains in branch-and-cut workflows. Conversely, confidence in end-to-end neural optimization remains low due to known theoretical boundaries—such as expressivity limits bounded by graph isomorphism tests, over-smoothing, and poor extrapolation when inputs diverge significantly from training distributions.

CERC in Data Science for Real-Time Decision-Making Cornell Tech and Technion - IIT Google Jacobs Technion-Cornell Institute Polytechnique Montréal RWTH Aachen University University of Toronto combinatorial optimization combinatorial problems graph neural networks graph neural networks combinatorial optimization neural algorithmic reasoning

arXiv: 2102.09544

Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). This seminal survey establishes the foundational taxonomy and conceptual frameworks for integrating machine learning into discrete optimization solvers that the source paper directly builds upon and expands.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). It provides the foundational framework for learning greedy combinatorial optimization heuristics directly over graph representations using graph embeddings and reinforcement learning.
Paper: Attention, Learn to Solve Routing Problems!, Wouter Kool et al. (2018). It introduces the influential attention-based encoder-decoder architecture for solving vehicle routing and traveling salesperson problems via reinforcement learning, a core primal optimization baseline evaluated in the survey.
Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). It introduces neural combinatorial optimization with reinforcement learning and policy gradients, establishing the primary methodology for training neural networks to solve discrete optimization problems without ground-truth labels.
Paper: Pointer networks, Oriol Vinyals et al. (2015). It introduces Pointer Networks, the foundational sequence-to-sequence mechanism for producing variable-length combinatorial permutation outputs like Traveling Salesperson Problem tours.
Paper: Relational inductive biases, deep learning, and graph networks, Peter W. Battaglia et al. (2018). It defines relational inductive biases and the encode-process-decode blueprint that underpins the neural algorithmic reasoning architectures discussed throughout the source.
Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). It establishes the Weisfeiler-Lehman theoretical limits on graph neural network expressiveness and discriminative power that the source cites as fundamental boundaries for end-to-end neural optimization.
Paper: OptNet: Differentiable Optimization as a Layer in Neural Networks, Brandon Amos et al. (2017). It develops differentiable optimization layers that enable exact mathematical programs to be embedded directly within deep learning architectures.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). It formalizes localized first-order spectral convolutions on graphs, providing the essential graph convolutional network formulation used in combinatorial reasoning.
Paper: A Comprehensive Survey on Graph Neural Networks, Zonghan Wu et al. (2019). It delivers a comprehensive taxonomy and foundational overview of graph neural network architectures necessary for understanding graph-based learning pipelines.

Paper: Learn from Global Correlations: Enhancing Evolutionary Algorithm via Spectral GNN, Kaichen Ouyang et al. (2026). Extends the hybrid optimization paradigm by using spectral graph neural networks to model search populations and adaptively balance exploration and exploitation in evolutionary algorithms.

Cover for Combinatorial Optimization and Reasoning with Graph Neural Networks

Abstract

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either directly as solvers or by enhancing exact solvers. The inductive bias of GNNs effectively encodes combinatorial and relational input due to their invariance to permutations and awareness of input sparsity. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at optimization and machine learning researchers.

Topics

combinatorial optimization combinatorial problems graph neural networks reasoning iterative solvers optimization problems

Keywords

graph neural networks combinatorial optimization neural algorithmic reasoning graph reasoning combinatorial solvers graph partitioning graph matching NP-complete problems pointer networks graph coloring

1. Introduction
1.1 What Are the Challenges for Machine Learning?
1.2 How Do GNNs Address These Challenges?
1.3 Going Beyond Classical Algorithms
1.4 Present Work
1.5 Related Work
1.6 Outline
2. Preliminaries
2.1 Notation
2.2 Combinatorial Optimization
2.3 General Optimization Frameworks: ILPs, SAT, and Constrained Problems
2.3.1 Integer linear programs and mixed-integer programs
2.3.2 SAT
2.3.3 Constraint satisfaction and constraint optimization problems
2.3.4 Solving CO problems
2.4 Machine Learning
2.5 Graph Neural Networks
3. GNNs for Combinatorial Optimization: The State of the Art
3.1 On the Primal Side: Finding Feasible Solutions
3.1.1 Supervised Learning
3.1.2 Unsupervised Learning
3.1.3 Reinforcement Learning for Iterative Solution Construction
3.1.4 Summary
3.2 On the Dual Side: Proving Optimality
3.2.1 Integer programming
3.2.2 Logic solving
3.2.3 Constraint programming
3.2.4 Decision diagrams
3.2.5 Summary
3.3 Algorithmic Reasoning
3.3.1 Algorithmic alignment
3.3.2 Perspectives and outlooks
3.3.3 Reasoning on natural inputs
3.3.4 Summary
4. Limitations and Research Directions
4.1 Limitations
4.2 Proposed New Directions
5. Implementation Frameworks
6. Conclusions
Acknowledgements and Disclosure of Funding
References

Knowls

Knowl 1 — Algorithmic Reasoning Blueprint for Combinatorial Optimization on Natural Inputs
model/method
The algorithmic reasoning blueprint provides a methodology for applying classical combinatorial algorithms to raw, noisy, or rich real-world inputs without manually compressing data into scalar proxy parameters.

The blueprint consists of three stages:
1. Algorithmic Reasoner Pre-training: Given an algorithm $A$ that operates on abstract inputs $\bar{x}$ , an algorithmic reasoner is trained on generated abstract instances in an encode-process-decode architecture: $g(P(f(\bar{x}))) \approx A(\bar{x})$ where $f: \mathcal{X}_{\text{abstract}} \to \mathcal{Z}$ is an encoder neural network, $P: \mathcal{Z} \to \mathcal{Z}$ is a processor Graph Neural Network (GNN) that performs latent computations emulating algorithm steps, and $g: \mathcal{Z} \to \mathcal{Y}_{\text{abstract}}$ is a decoder network.
2. Processor Transfer: The trained processor $P$ is frozen, preserving the learned high-dimensional execution dynamics of $A$ .
3. Natural Input Integration: New encoder $\tilde{f}: \mathcal{X}_{\text{raw}} \to \mathcal{Z}$ and decoder $\tilde{g}: \mathcal{Z} \to \mathcal{Y}$ networks are connected to $P$ . The end-to-end model $\tilde{g}(P(\tilde{f}(x)))$ is trained via gradient descent on natural inputs $x$ , allowing $\tilde{f}$ to learn differentiable representations that map directly into the latent algorithmic space of $P$ without information-bottlenecked scalar abstractions.
Knowl 2 — Algorithmic Alignment of Graph Neural Networks with Dynamic Programming
theoretical result
A neural network architecture is algorithmically aligned with an algorithm if the algorithm can be decomposed into sub-computations that each correspond directly to modules of the network. Graph Neural Networks (GNNs) align naturally with polynomial-time dynamic programming recursions.

For instance, the Bellman-Ford dynamic programming update for shortest paths is given by: $d_u = \min_{v \in \mathcal{N}(u)} (d_v + w_{vu})$ where $d_u \in \mathbb{R}$ is the distance estimate to node $u$ , $\mathcal{N}(u)$ denotes the neighborhood of $u$ , and $w_{vu}$ is the edge weight between $v$ and $u$ .

A message-passing GNN update with component-wise maximum aggregation: $h'_u = \max_{v \in \mathcal{N}(u)} M(h_u, h_v, w_{vu})$ where $h_u, h_v$ are latent node features and $M$ is a parameterized message function, aligns directly with this update. Because multilayer perceptrons using ReLU activations extrapolate linearly outside the support of their training distribution, message functions $M$ that only need to learn linear operations (such as $d_v + w_{vu}$ ) extrapolate accurately to out-of-distribution graph sizes and structures, whereas sum-aggregation GNNs fail to achieve comparable out-of-distribution generalization.
Knowl 3 — Architectural and Training Prescriptions for Neural Algorithmic Reasoners
model/method
To enable Graph Neural Networks (GNNs) to faithfully execute combinatorial algorithms and generalize out-of-distribution, five core architectural and training prescriptions are established:
1. Encode-Process-Decode Paradigm: Inputs $x \in \mathcal{X}$ are embedded into latent representations $z \in \mathcal{Z}$ via an encoder $f: \mathcal{X} \to \mathcal{Z}$ , updated through a recurrent processor GNN $P: \mathcal{Z} \to \mathcal{Z}$ executed for multiple steps, and decoded into outputs $y \in \mathcal{Y}$ via $g: \mathcal{Z} \to \mathcal{Y}$ . This decouples representation extraction from algorithmic execution.
2. Component-wise Max Aggregation: Neighborhood aggregation using $\max$ rather than sum aligns with local extremum and selection decisions in combinatorial algorithms and provides numerical stability across varying neighborhood degrees.
3. Strong Supervision via Teacher Forcing: Rather than training exclusively on final inputs and outputs, intermediate execution traces of the ground-truth algorithm are used as step-by-step supervision targets during training, acting as an inductive regularizer.
4. Node and Output Masking: The network learns a explicit mask indicating which subset of nodes is active at each algorithmic step, preventing spurious updates to inactive nodes.
5. Multi-Task Reasoner Sharing: A single processor network $P$ is trained across multiple related algorithms, reinforcing shared algorithmic primitives (e.g., priority queue operations shared between Dijkstra's and Prim's algorithms).
Knowl 4 — Graph Representations for General Combinatorial Optimization Frameworks
model/method
Graph Neural Networks process combinatorial optimization problems by representing instances as structured graphs that preserve permutation invariance and exploit sparsity:
- Mixed-Integer Linear Programs (MIPs): An instance with constraint matrix $A \in \mathbb{R}^{m \times n}$ is represented as a bipartite graph $G = (V_{\text{var}} \cup V_{\text{con}}, E)$ , where $V_{\text{var}}$ has $n$ variable nodes, $V_{\text{con}}$ has $m$ constraint nodes, and an undirected edge $(v_i, c_j) \in E$ exists if $A_{ji} \ne 0$ . Edge attributes encode coefficients $A_{ji}$ , while node attributes encode objective coefficients, variable bounds, types (binary, integer, continuous), and constraint right-hand sides. Alternatively, a tripartite graph adds an explicit objective node connected to all variables.
- Boolean Satisfiability (SAT): A propositional formula in conjunctive normal form is represented as a bipartite graph between variable/literal nodes and clause nodes, where edges connect variables to the clauses in which they appear, labeled by variable polarity (negated or non-negated).
- Constraint Satisfaction Problems (CSPs): Represented as a tripartite graph consisting of variable nodes, domain value nodes, and constraint nodes. Edges connect variables to their domain values and constraints to their participating variables.
Knowl 5 — GNN-Guided Exact Solvers for Dual Bounds and Optimality Proofs
model/method
To certify optimality or prove infeasibility in combinatorial optimization, GNNs are integrated into exact tree search frameworks to guide critical discrete decisions:
1. Variable Selection (Branching): In branch-and-bound for MIPs, choosing which variable to branch on at each tree node determines search tree size. A GNN operating on the bipartite MIP graph is trained via imitation learning to mimic strong branching (an accurate but computationally expensive heuristic), yielding faster overall solving times and generalizing to larger problem instances.
2. Cutting Plane Selection: In branch-and-cut, solvers generate candidate valid inequalities (cuts) to tighten continuous LP relaxations. GNNs evaluate and rank generated cuts on tripartite graph representations to select the most effective subset without creating excessive LP solver overhead.
3. Decision Diagram Variable Ordering: Relaxed decision diagrams yield dual bounds whose tightness depends on variable processing order. GNNs trained via reinforcement learning predict sequential variable additions, providing dual bounds for problems such as maximum independent set that outperform standard linear relaxations.
Knowl 6 — Primal Solution Paradigms for GNN-Based Combinatorial Optimization
model/method
Graph Neural Networks find feasible (primal) solutions for combinatorial problems under three main paradigms:
1. Supervised Learning with Search: GNNs predict continuous assignments or component selection probabilities (e.g., edge inclusion probabilities for the Traveling Salesperson Problem). Because raw GNN predictions can violate hard constraints, they are post-processed using beam search, local branching, or solver-based repair methods (such as neural diving, where unassigned variables are resolved by an exact sub-solver).
2. Unsupervised Relaxations and Probabilistic Penalties: GNNs directly optimize continuous relaxations of objective functions with penalty terms for constraint violations (e.g., relaxing Quadratic Unconstrained Binary Optimization variables to $[0, 1]$ followed by threshold rounding). Probabilistic penalty frameworks output node subset distributions and apply sequential derandomization to guarantee constraint satisfaction with high probability.
3. Reinforcement Learning for Iterative Construction: Combinatorial problems are framed as Markov Decision Processes (MDPs) where a GNN parameterizes value functions (e.g., S2V-DQN) or autoregressive attention-based policies (e.g., REINFORCE on graph attention networks). For constrained problems (e.g., TSP with Time Windows), feasibility is maintained by masking invalid actions, applying deferred MDPs, or structuring hierarchical reward functions.
Knowl 7 — Theoretical Expressivity and Approximation Limits of GNNs in Combinatorial Optimization
theoretical result
The representational and computational power of standard message-passing Graph Neural Networks on combinatorial optimization tasks is bounded by theoretical limits:
- 1-Weisfeiler-Leman (1-WL) Upper Bound: The ability of standard message-passing GNNs to distinguish non-isomorphic graphs is upper-bounded by the 1-WL color refinement algorithm. Consequently, there exist pairs of structurally non-equivalent MIP instances (encoded as bipartite graphs) that produce identical GNN node and graph embeddings, rendering the GNN incapable of distinguishing them.
- Approximation Ratio Lower Bounds: Due to connections with distributed local algorithms, standard GNNs using local neighborhood aggregation cannot achieve an approximation ratio better than $2$ on the minimum vertex cover problem, which is suboptimal compared to classical algorithms. Analogous approximation suboptimality holds for the minimum dominating set and maximum matching problems.
- Computability Constraints: Sub-linear depth or width GNNs cannot compute global graph properties, such as graph diameter or minimum spanning tree construction, unless depth and width scale adequately with problem size.
Knowl 8 — Inference Latency Overhead in GNN-Augmented Exact Solvers
limitation
Within branch-and-bound or branch-and-cut solvers, decision routines (such as variable branching) are evaluated at every node of a search tree, often totaling tens of thousands of invocations per instance.

While GNN-guided policies can significantly reduce the total number of explored search nodes compared to hand-crafted heuristics, the polynomial computational complexity of evaluating a deep GNN at every search node introduces substantial wall-clock overhead. Because solver internal operations cannot easily be batched or parallelized on GPUs, running full GNN inference repeatedly often results in longer total execution time than fast, human-designed heuristics (such as pseudo-cost branching).

To address this overhead, solvers utilize hybrid execution models: full GNN inference is run once at the root node to compute high-level embeddings, and subsequent node decisions are delegated to lightweight multilayer perceptrons (MLPs) or fast heuristics.
Knowl 9 — Generalization, Over-smoothing, and Over-squashing Bottlenecks in GNN Optimizers
limitation
Applying GNNs to large-scale combinatorial optimization tasks is constrained by three fundamental structural bottlenecks:
1. Out-of-Distribution Size Generalization Drop: GNN generalization bounds depend inversely on input graph sparsity and maximum node degree. GNN models trained on small synthetic instances (e.g., TSP with 50 nodes) exhibit severe performance drops when evaluated on larger or denser instances.
2. Over-smoothing: Stacking multiple message-passing layers to propagate long-range information across large graphs causes node embeddings to exponentially converge toward uniform representations, destroying local node distinctiveness required for variable/constraint decisions.
3. Over-squashing: In graphs with high connectivity or large neighborhoods, an exponential number of multi-hop neighborhood features is compressed into fixed-size latent vectors. This information bottleneck prevents GNNs from capturing long-range dependencies necessary to verify global constraints.
Knowl 10 — Data Generation Triviality for NP-Hard Problems Under Computational Assumptions
theoretical result
Assuming $\text{P} \ne \text{NP}$ (and $\text{NP} \ne \text{co-NP}$ ), any polynomial-time sample generator designed to produce instances of an NP-hard decision problem necessarily samples from a strictly easier sub-problem that is solvable in polynomial time.

Under specific generator distributions, the sampled problem instances become trivially classifiable based on simple local features or statistical artifacts (e.g., checking a single input feature). As a result, supervised GNN classifiers evaluated on synthetically generated NP-hard datasets can achieve artificially inflated performance metrics that fail to transfer to worst-case instances or realistic industrial problem distributions.

Coverage note — Deliberately omitted individual external software library API details (e.g., specific functions of PyTorch Geometric, DGL, Ecole, OR-Gym) and specific empirical benchmark scores on individual datasets, focusing on the conceptual survey frameworks, formal models, theoretical bounds, and architectural paradigms.

References

1.R. Abboud, I. Ceylan, and T. Lukasiewicz. Learning to reason: Leveraging neural networks for approximate dnf counting. In AAAI Conference on Artificial Intelligence, pages 3097–3104, 2020.
2.R. Abboud, I. I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. In International Joint Conference on Artificial Intelligence, pages 2112–2118, 2021.
3.K. Abe, I. Sato, and M. Sugiyama. Solving NP-hard problems on graphs by reinforcement learning without domain knowledge. Simulation, 1:1–1, 2019.
4.S. Ahn, Y. Seo, and J. Shin. Learning what to defer for maximum independent sets. In International Conference on Machine Learning, pages 134–144, 2020.
5.U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint, abs/2006.05205, 2020.
6.S. Amizadeh, S. Matusevych, and M. Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Representations, 2018.
7.M. C. Angelini and F. Ricci-Tersenghi. Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms. arXiv preprint arXiv:2206.13211, 2022.
8.S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Conference on Foundations of Computer Science, pages 2–11, 1996.
9.V. Arvind, J. K¨obler, G. Rattan, and O. Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pages 339–350, 2015.
10.G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
11.P. Awasthi, A. Das, and S. Gollapudi. Beyond GNNs: A sample efficient architecture for graph problems. In AAAI Conference on Artificial Intelligence, 2022.
12.Y. Bai, H. Ding, K. Gu, Y. Sun, and W. Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In AAAI Conference on Artificial Intelligence, pages 3219–3226, 2020.
13.A. Bansal, A. Schwarzschild, E. Borgnia, Z. Emam, F. Huang, M. Goldblum, and T. Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In Advances in Neural Information Processing Systems, 2022.
14.G. Behnke, D. H¨oller, and S. Biundo. totsat-totally-ordered hierarchical planning through sat. In AAAI Conference on Artificial Intelligence, 2018.
15.N. Beldiceanu, M. Carlsson, and J.-X. Rampon. Global constraint catalog. 2005.
16.R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.
17.R. Bellman. Dynamic programming. Science, 153(3731):34–37, 1966.
18.I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representations, 2017.
19.V. E. Beneš et al. Mathematical theory of connecting networks and telephone traffic. Academic press, 1965.
20.Y. Bengio, J. Louradour, R. Collobert, and J. Weston. Curriculum learning. In International Conference on Machine Learning, pages 41–48, 2009.
21.Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.
22.D. Bergman, A. A. Cire, W.-J. Van Hoeve, and J. Hooker. Decision diagrams for optimization, volume 1. Springer, 2016.
23.D. Bertsimas and J. Tsitsiklis. Introduction to linear optimization. Athena Scientific, 1997.
24.L. Beurer-Kellner, M. Vechev, L. Vanbever, and P. Veličković. Learning to configure computer networks with neural algorithmic reasoning. In Advances in Neural Information Processing Systems, 2022.
25.B. Bevilacqua, Y. Zhou, and B. Ribeiro. Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837–851, 2021.
26.C. Blundell, L. Buesing, A. Davies, P. Veličković, and G. Williamson. Towards combinatorial invariance for Kazhdan-Lusztig polynomials. Representation Theory, 2022.
27.M. B¨other, O. Kißig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich. What’s wrong with deep learning in tree search for combinatorial optimization. arXiv preprint arXiv:2201.10494, 2022.
28.I. Boussa¨ıd, J. Lepagnot, and P. Siarry. A survey on optimization metaheuristics. Information sciences, 237:82–117, 2013.
29.X. Bresson and T. Laurent. Residual gated graph convnets. arXiv preprint, abs/1711.07553, 2017.
30.G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAI Gym. CoRR, abs/1606.01540, 2016.
31.C. Brouard, S. de Givry, and T. Schiex. Pushing data into cp models using graphical model learning and solving. In International Conference on Principles and Practice of Constraint Programming, pages 811–827, 2020.
32.C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012.
33.J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference on Learning Representation, 2014.
34.C. Cameron, R. Chen, J. S. Hartford, and K. Leyton-Brown. Predicting propositional satisfiability via end-to-end learning. In AAAI Conference on Artificial Intelligence, pages 3324–3331, 2020.
35.Q. Cappart, E. Goutierre, D. Bergman, and L.-M. Rousseau. Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. In AAAI Conference on Artificial Intelligence, pages 1443–1451, 2019.
36.Q. Cappart, T. Moisan, L.-M. Rousseau, I. Prémont-Schwarz, and A. A. Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. In AAAI Conference on Artificial Intelligence, pages 3677–3687, 2021.
37.Q. Cappart, D. Bergman, L.-M. Rousseau, I. Prémont-Schwarz, and A. Parjadis. Improving variable orderings of approximate decision diagrams using reinforcement learning. INFORMS Journal on Computing, 2022.
38.F. Chalumeau, I. Coulon, Q. Cappart, and L.-M. Rousseau. SeaPearl: A constraint programming solver guided by reinforcement learning. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 392–409, 2021.
39.I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy. Machine learning on graphs: A model and comprehensive taxonomy. arXiv preprint, abs/2005.03675, 2020.
40.T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597–1607, 2020.
41.Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems, pages 15868–15876, 2019.
42.C. Chi, A. Aboussalah, E. Khalil, J. Wang, and Z. Sherkat-Masoumi. A deep reinforcement learning framework for column generation. Advances in Neural Information Processing Systems, 35:9633–9644, 2022.
43.E. Clarke, M. Talupur, H. Veith, and D. Wang. Sat based predicate abstraction for hardware verification. In International Conference on Theory and Applications of Satisfiability Testing, pages 78–92, 2003.
44.S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pages 151–158, 1971.
45.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
46.G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, pages 13260–13271, 2020.
47.R. Csordas and J. Schmidhuber. Improving differentiable neural computers through memory masking, de-allocation, and link distribution sharpness control. International Conference on Learning Representations, 2019.
48.H. Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In International Conference on Machine Learning, pages 2702–2711, 2016.
49.H. Dai, E. Khalil, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pages 6348–6358, 2017.
50.A. Davies, P. Veličković, L. Buesing, S. Blackwell, D. Zheng, N. Tomašev, R. Tanburn, P. Battaglia, C. Blundell, A. Juhász, M. Lackenby, G. Williamson, D. Hassabis, and P. Kohli. Advancing mathematics by guiding human intuition with ai. Nature, 600(7887): 70–74, 2021.
51.L. de Moura and N. Bjørner. Z3: An efficient smt solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340. Springer, 2008.
52.A. Deac, P. Bacon, and J. Tang. Graph neural induction of value iteration. arXiv preprint, abs/2009.12604, 2020.
53.A. Deac, P. Veličković, O. Milinkovic, P.-L. Bacon, J. Tang, and M. Nikolic. Neural algorithmic reasoners are implicit planners. Advances in Neural Information Processing Systems, 2021.
54.M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3844–3852, 2016.
55.D. Delahaye, S. Chaimatanan, and M. Mongeau. Simulated annealing: From basics to applications. In Handbook of metaheuristics, pages 1–35. Springer, 2019.
56.M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau. Learning heuristics for the TSP by policy gradient. In International conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 170–181, 2018.
57.E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, 1959.
58.J.-Y. Ding, C. Zhang, L. Shen, S. Li, B. Wang, Y. Xu, and L. Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In AAAI Conference on Artificial Intelligence, 2020.
59.E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, volume 11, pages 1277–1280, 1970.
60.A. Draguns, E. Ozoliņš, A. Šostaks, M. Apinis, and K. Freivalds. Residual shuffle-exchange networks for fast processing of long sequences. In AAAI Conference on Artificial Intelligence, pages 7245–7253, 2021.
61.J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86–124, 1989.
62.M. Dror, G. Laporte, and P. Trudeau. Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3):239–254, 1994.
63.I. Drori, A. Kharkar, W. R. Sickinger, B. Kates, Q. Ma, S. Ge, E. Dolev, B. Dietrich, D. P. Williamson, and M. Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In IEEE International Conference on Machine Learning and Applications, pages 19–24, 2020.
64.H. Duan, P. Vaezipoor, M. B. Paulus, Y. Ruan, and C. Maddison. Augment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning, pages 5627–5642, 2022.
65.A. J. Dudzik and P. Veličković. Graph neural networks are dynamic programmers. In Advances in Neural Information Processing Systems, 2022.
66.R. Durbin and D. Willshaw. An analogue approach to the travelling salesman problem using an elastic net method. Nature, 326(6114):689–691, 1987.
67.D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pages 2224–2232, 2015.
68.V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. arXiv preprint, abs/2003.00982, 2020.
69.K. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248–264, 1972.
70.M. Etheve, Z. Alès, C. Bissuel, O. Juan, and S. Kedad-Sidhoum. Reinforcement learning for variable selection in a branch and bound algorithm. In CPAIOR, 2020.
71.G. Farquhar, T. Rockt¨aschel, M. Igl, and S. Whiteson. TreeQN and ATreeC: Differentiable tree-structured models for deep reinforcement learning. In International Conference on Learning Representations, 2018.
72.P. Festa. A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In International Conference on Transparent Optical Networks, pages 1–20, 2014.
73.M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. arXiv preprint, abs/1903.02428, 2019.
74.M. Fey, J. E. Lenssen, C. Morris, J. Masci, and N. M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2020.
75.M. Fischetti and A. Lodi. Local branching. Mathematical Programming, 98(1-3):23–47, 2003.
76.L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956.
77.L. R. Ford and D. R. Fulkerson. Flows in networks. Princeton University Press, 2015.
78.A. François, Q. Cappart, and L.-M. Rousseau. How to evaluate machine learning approaches for combinatorial optimization: Application to the travelling salesman problem. arXiv preprint, abs/1909.13121, 2019.
79.K. Freivalds, E. Ozoliņš, and Šostaks. Neural shuffle-exchange networks-sequence processing in O(n log n) time. In Advances in Neural Information Processing Systems, pages 6626–6637, 2019.
80.A. Galler, B and M. J. Fisher. An improved equivalence algorithm. Communications of the ACM, 7(5):301–303, 1964.
81.G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig, G. Hendel, C. Hojny, T. Koch, P. Le Bodic, S. J. Maher, F. Matter, M. Miltenberger, E. M¨uhmer, B. M¨uller, M. E. Pfetsch, F. Schl¨osser, F. Serrano, Y. Shinano, C. Tawfik, S. Vigerske, F. Wegscheider, D. Weninger, and J. Witzig. The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin, March 2020.
82.V. Ganesh and M. Y. Vardi. On the unreasonable effectiveness of sat solvers, 2020.
83.V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419–3430, 2020.
84.M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 15554–15566, 2019.
85.M. Gasse, S. Bowly, Q. Cappart, J. Charfreitag, L. Charlin, D. Chételat, A. Chmiela, J. Dumouchelle, A. Gleixner, A. M. Kazachkov, E. Khalil, P. Lichocki, A. Lodi, M. Lubin, C. J. Maddison, C. Morris, D. J. Papageorgiou, A. Parjadis, S. Pokutta, A. Prouvost, L. Scavuzzo, G. Zarpellon, L. Yang, S. Lai, A. Wang, X. Luo, X. Zhou, H. Huang, S. Shao, Y. Zhu, D. Zhang, T. Quan, Z. Cao, Y. Xu, Z. Huang, S. Zhou, B. Chen, M. He, H. Hao, Z. Zhang, Z. An, and M. Kun. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurIPS 2021 Competitions and Demonstrations Track, pages 220–231, 2022.
86.D. Georgiev and P. Lió. Neural bipartite matching. arXiv preprint, abs/2005.11304, 2020.
87.D. Georgiev, P. Barbiero, D. Kazhdan, P. Veličković, and P. Liò. Algorithmic concept-based explainable reasoning. In AAAI Conference on Artificial Intelligence, pages 6685–6693, 2022.
88.J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
89.A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bastubbe, T. Berthold, P. M. Christophel, K. Jarck, T. Koch, J. Linderoth, M. L¨ubbecke, H. D. Mittelmann, D. Ozyurt, T. K. Ralphs, D. Salvagnin, and Y. Shinano. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 2020.
90.F. Glover and M. Laguna. Tabu search. In Handbook of combinatorial optimization, pages 2093–2229. Springer, 1998.
91.F. W. Glover and G. A. Kochenberger. Handbook of metaheuristics, volume 57. Springer Science & Business Media, 2006.
92.S. Gold, A. Rangarajan, et al. Softmax to softassign: Neural network algorithms for combinatorial optimization. Journal of Artificial Neural Networks, 2(4):381–399, 1996.
93.A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921–940, 1988.
94.A. Graves, G. Wayne, and I. Danihelka. Neural Turing machines. arXiv preprint, abs/1410.5401, 2014.
95.A. Graves, G. Wayne, M. Reynolds, T. Harley, I. Danihelka, A. Grabska-Barwińska, S. Gómez Colmenarejo, E. Grefenstette, T. Ramalho, J. Agapiou, A. Badia Puigdomènech, K. M. Hermann, Y. Zwols, G. Ostrovski, A. Cain, H. King, C. Summerfield, P. Blunsom, K. Kavukcuoglu, and D. Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471–476, 2016.
96.A. Gupta, M. K. Ganai, and C. Wang. SAT-based verification methods and applications in hardware verification. In International School on Formal Methods for the Design of Computer, Communication and Software Systems, pages 108–143, 2006.
97.P. Gupta, M. Gasse, E. Khalil, P. Mudigonda, A. Lodi, and Y. Bengio. Hybrid models for learning to branch. Advances in Neural Information Processing Systems, 33:18087–18097, 2020.
98.A. Guzman-Rivera, D. Batra, and P. Kohli. Multiple choice learning: Learning to produce multiple structured outputs. In Advances in Neural Information Processing Systems, pages 1808–1816, 2012.
99.W. Hamilton, P. Bajaj, M. Zitnik, D. Jurafsky, and J. Leskovec. Embedding logical queries on knowledge graphs. Advances in neural information processing systems, 31, 2018.
100.W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025–1035, 2017.
101.J. B. Hamrick, K. R. Allen, V. Bapst, T. Zhu, K. R. McKee, J. B. Tenenbaum, and P. W. Battaglia. Relational inductive bias for physical construction in humans and machines. In Annual Meeting of the Cognitive Science Society, 2018.
102.P. Hansen, N. Mladenović, J. Brimberg, and J. A. M. Pérez. Variable neighborhood search. In Handbook of metaheuristics, pages 57–97. Springer, 2019.
103.T. E. Harris and F. S. Ross. Fundamentals of a method for evaluating rail net capacities. Technical report, RAND Coperation, Santa Monica, CA, 1955.
104.Y. He, P. Veličković, P. Lio, and A. Deac. Continuous neural algorithmic planners. In The First Learning on Graphs Conference, 2022. URL https://openreview.net/forum?id=60avttW0Mv.
105.K. Helsgaun. An effective implementation of the Lin–Kernighan traveling salesman heuristic. European journal of operational research, 126(1):106–130, 2000.
106.K. Helsgaun. General k-opt submoves for the lin–kernighan tsp heuristic. Mathematical Programming Computation, 1:119–163, 2009.
107.J. J. Hopfield and D. W. Tank. “Neural” computation of decisions in optimization problems. Biological cybernetics, 52(3):141–152, 1985.
108.C. D. Hubbs, H. D. Perez, O. Sarwar, N. V. Sahinidis, I. E. Grossmann, and J. M. Wassick. OR-Gym: A reinforcement learning library for operations research problems. arXiv preprint, abs/2008.06319, 2020.
109.A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys, 50(2):1–35, 2017.
110.B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, R. Csordás, A. J. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, A. Deac, B. Bevilacqua, Y. Ganin, C. Blundell, and P. Veličković. A generalist neural algorithmic learner. In The First Learning on Graphs Conference, 2022.
111.C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint, abs/1906.01227, 2019.
112.C. K. Joshi, Q. Cappart, L.-M. Rousseau, and T. Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, pages 1–29, 2022.
113.N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, et al. In-datacenter performance analysis of a tensor processing unit. In Annual International Symposium on Computer Architecture, pages 1–12, 2017.
114.L. Kaiser and I. Sutskever. Neural GPUs learn algorithms. arXiv preprint, abs/1511.08228, 2015.
115.G. Karakostas. A better approximation ratio for the vertex cover problem. In International Colloquium on Automata, Languages, and Programming, pages 1043–1050. Springer, 2005.
116.N. Karalias and A. Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Advances in Neural Information Processing Systems, 2020.
117.R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972.
118.E. B. Khalil, C. Morris, and A. Lodi. MIP-GNN: A data-driven framework for guiding combinatorial solvers. In AAAI Conference on Artificial Intelligence, 2022.
119.T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representation, 2017.
120.D. B. Kireev. Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemical Information and Computer Sciences, 35(2):175–180, 1995.
121.P. Kn¨obelreiter, C. Reinbacher, A. Shekhovtsov, and T. Pock. End-to-end training of hybrid cnn-crf models for stereo. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2339–2348, 2017.
122.W. Kool, H. Van Hoof, and M. Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
123.B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 5th edition, 2012.
124.J. Kotary, F. Fioretto, P. Van Hentenryck, and B. Wilder. End-to-end constrained optimization learning: A survey. In International Joint Conference on Artificial Intelligence, pages 4475–4482, 8 2021.
125.O. Kramer. Genetic algorithms. In Genetic algorithm essentials, pages 11–19. Springer, 2017.
126.K. Kurach, M. Andrychowicz, and I. Sutskever. Neural random-access machines. arXiv preprint, abs/1511.06392, 2015.
127.V. Kurin, S. Godil, S. Whiteson, and B. Catanzaro. Can Q-learning with graph networks learn a generalizable branching heuristic for a SAT solver? In Advances in Neural Information Processing Systems, 2020.
128.A. G. Labassi, D. Chételat, and A. Lodi. Learning to compare nodes in branch and bound with graph neural networks. In Advances in Neural Information Processing Systems, volume 35, pages 32000–32010, 2022.
129.M. Laguna. Tabu search. In Handbook of heuristics, pages 741–758. Springer, 2018.
130.L. C. Lamb, A. S. d’Avila Garcez, M. Gori, M. O. R. Prates, P. H. C. Avelar, and M. Y. Vardi. Graph neural networks meet neural-symbolic computing: A survey and perspective. In International Joint Conference on Artificial Intelligence, pages 4877–4884, 2020.
131.A. Land and A. Doig. An automatic method of solving discrete programming problems. Econometrica, 28:497–520, 1960.
132.G. Lederman, M. N. Rabe, and S. A. Seshia. Learning heuristics for automated reasoning through deep reinforcement learning. In International Conference on Learning Representations, 2020.
133.H. Lemos, M. Prates, P. Avelar, and L. Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. In IEEE International Conference on Tools with Artificial Intelligence, pages 879–885, 2019.
134.Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference on Artificial Intelligence, pages 3538–3545, 2018a.
135.Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In International Conference on Machine Learning, pages 3835–3845, 2019.
136.Y. Li, F. Gimeno, P. Kohli, and O. Vinyals. Strong generalization and efficiency in neural programs. arXiv preprint, abs/2007.03629, 2020.
137.Z. Li, Q. Chen, and V. Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pages 537–546, 2018b.
138.Z. Li, Q. Chen, and V. Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in Neural Information Processing Systems, 31, 2018c.
139.D. Liu, A. Lodi, and M. Tanneau. Learning chordal extensions. Journal of Global Optimization, 81(1):3–22, 2021.
140.D. Liu, M. Fischetti, and A. Lodi. Learning to search in local branching. In AAAI Conference on Artificial Intelligence, pages 3796–3803, 2022.
141.A. Lodi. Mixed integer programming computation. In 50 years of integer programming 1958-2008, pages 619–645. Springer, Berlin, Heidelberg, 2010.
142.A. Lodi. The heuristic (dark) side of MIP solvers. In Hybrid metaheuristics, pages 273–284. Springer, 2013.
143.A. Lodi and G. Zarpellon. On learning and branching: A survey. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 25(2):207–236, July 2017.
144.A. Loukas. What graph neural networks cannot learn: Depth vs width. In International Conference on Learning Representations, 2020.
145.K. Lu and M. P. Kumar. Neural network branching for neural network verification. In International Conference on Learning Representations, 2020.
146.Q. Ma, S. Ge, D. He, D. Thaker, and I. Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint, abs/1911.04936, 2019.
147.A. Madsen and A. R. Johansen. Neural arithmetic units. In International Conference on Learning Representations, 2020.
148.F. Mancinelli, J. Boender, R. Di Cosmo, J. Vouillon, B. Durak, X. Leroy, and R. Treinen. Managing the complexity of large free and open source package-based software distributions. In IEEE/ACM International Conference on Automated Software Engineering, pages 199–208, 2006.
149.J. Mandi and T. Guns. Interior point solving for LP-based prediction+optimisation. In Advances in Neural Information Processing Systems, 2020.
150.H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pages 2153–2164, 2019a.
151.H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
152.J. Marques-Silva, I. Lynce, and S. Malik. Conflict-driven clause learning SAT solvers. In Handbook of Satisfiability, pages 133–182. 2021.
153.N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
154.C. Merkwirth and T. Lengauer. Automatic generation of complementary descriptors with molecular graph networks. Journal of Chemical Information and Modeling, 45(5):1159–1168, 2005.
155.A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):207–212, 2021.
156.N. Mladenović and P. Hansen. Variable neighborhood search. Computers & operations research, 24(11):1097–1100, 1997.
157.M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
158.F. Monti, D. Boscaini, J. Masci, E. Rodolà, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition, pages 5425–5434, 2017.
159.M. Morabit, G. Desaulniers, and A. Lodi. Machine-learning–based column selection for column generation. Transportation Science, 55(4):815–831, 2021.
160.C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Conference on Artificial Intelligence, pages 4602–4609, 2019.
161.C. Morris, G. Rattan, and P. Mutzel. Weisfeiler and Leman go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020.
162.C. Morris, M. Fey, and N. M. Kriege. The power of the Weisfeiler-Leman algorithm for machine learning with graphs. In International Joint Conference on Artificial Intelligence, pages 4543–4550, 2021.
163.R. L. Murphy, B. Srinivasan, V. A. Rao, and B. Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663–4673, 2019a.
164.R. L. Murphy, B. Srinivasan, V. A. Rao, and B. Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. In International Conference on Learning Representations, 2019b.
165.V. Nair, S. Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraatmadja, P. Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint, abs/2012.13349, 2020.
166.M. Nazari, A. Oroojlooy, M. Takáč, and L. V. Snyder. Reinforcement learning for solving the vehicle routing problem. In International Conference on Neural Information Processing Systems, pages 9861–9871, 2018.
167.M. Niepert, P. Minervini, and L. Franceschi. Implicit MLE: backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, pages 14567–14579, 2021.
168.S. Niu, S. Chen, H. Guo, C. Targonski, M. Smith, and J. Kovačević. Generalized value iteration networks: Life beyond lattices. In AAAI Conference on Artificial Intelligence, 2018.
169.A. Nowak, S. Villar, A. S. Bandeira, and J. Bruna. Revised note on learning quadratic assignment with graph neural networks. In IEEE Data Science Workshop, pages 1–5, 2018.
170.D. Numeroso, D. Bacciu, and P. Veličković. Dual algorithmic reasoning. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=hhvkdRdWt1F.
171.E. Ong and P. Veličković. Learnable commutative monoids for graph neural networks. In The First Learning on Graphs Conference, 2022.
172.E. Ozolins, K. Freivalds, A. Draguns, E. Gaile, R. Zakovskis, and S. Kozlovics. Goal-aware neural SAT solver. In International Joint Conference on Neural Networks, pages 1–8, 2022.
173.R. Palm, U. Paquet, and O. Winther. Recurrent relational networks. Advances in Neural Information Processing Systems, 31, 2018.
174.A. Parjadis, Q. Cappart, L.-M. Rousseau, and D. Bergman. Improving branch-and-bound using decision diagrams and reinforcement learning. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 446–455, 2021.
175.M. B. Paulus, G. Zarpellon, A. Krause, L. Charlin, and C. Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International Conference on Machine Learning, pages 17584–17600, 2022.
176.T. Pfaff, M. Fortunato, A. Sanchez-Gonzalez, and P. Battaglia. Learning mesh-based simulation with graph networks. In International Conference on Learning Representations, 2020.
177.A. S. Polydoros and L. Nalpantidis. Survey of model-based reinforcement learning: Applications on robotics. Journal of Intelligent & Robotic Systems, 86(2):153–173, 2017.
178.J.-Y. Potvin and M. Gendreau. Handbook of Metaheuristics. Springer, 2018.
179.M. R. Prasad, A. Biere, and A. Gupta. A survey of recent advances in sat-based formal verification. International Journal on Software Tools for Technology Transfer, 7(2):156–173, 2005.
180.M. Prates, P. H. C. Avelar, H. Lemos, L. C. Lamb, and M. Y. Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In AAAI Conference on Artificial Intelligence, pages 4731–4738, 2019.
181.R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):1389–1401, 1957.
182.A. Pritzel, B. Uria, S. Srinivasan, A. P. Badia, O. Vinyals, D. Hassabis, D. Wierstra, and C. Blundell. Neural episodic control. In International Conference on Machine Learning, pages 2827–2836, 2017.
183.A. Prouvost, J. Dumouchelle, L. Scavuzzo, M. Gasse, D. Chételat, and A. Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. arXiv preprint, abs/2011.06069, 2020.
184.J. Ramanujam and P. Sadayappan. Mapping combinatorial optimization problems onto neural networks. Information sciences, 82(3-4):239–255, 1995.
185.S. Reed and N. De Freitas. Neural programmer-interpreters. arXiv preprint, abs/1511.06279, 2015.
186.J.-C. Régin. A filtering algorithm for constraints of difference in CSPs. In National Conference on Artificial Intelligence, pages 362–367, 1994.
187.J.-C. Régin. Global constraints and filtering algorithms. In Constraint and Integer Programming, pages 89–135. Springer, 2004.
188.H. Ren, W. Hu, and J. Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2019.
189.O. Richter and R. Wattenhofer. Normalized attention without probability cage. arXiv preprint, abs/2005.09561, 2020.
190.S. Ross. Interactive Learning for Sequential Decisions and Predictions. PhD thesis, Carnegie Mellon University, 2013.
191.F. Rossi, P. Van Beek, and T. Walsh. Handbook of constraint programming. Elsevier, 2006.
192.A. Sanchez-Gonzalez, J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning, pages 8459–8468, 2020.
193.A. Santoro, D. Raposo, D. G. Barrett, M. Malinowski, R. Pascanu, P. Battaglia, and T. Lillicrap. A simple neural network module for relational reasoning. In Advances in Neural Information Processing Systems, pages 4967–4976, 2017.
194.A. Santoro, R. Faulkner, D. Raposo, J. Rae, M. Chrzanowski, T. Weber, D. Wierstra, O. Vinyals, R. Pascanu, and T. Lillicrap. Relational recurrent neural networks. In Advances in Neural Information Processing Systems, pages 7299–7310, 2018.
195.R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pages 4083–4092, 2019.
196.R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In SIAM International Conference on Data Mining, pages 333–341. SIAM, 2021.
197.M. W. P. Savelsbergh. Local search in routing problems with time windows. Annals of Operations research, 4(1):285–305, 1985.
198.F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009.
199.L. Scavuzzo, F. Chen, D. Chételat, M. Gasse, A. Lodi, N. Yorke-Smith, and K. Aardal. Learning to branch with tree mdps. In Advances in Neural Information Processing Systems, volume 35, pages 18514–18526, 2022.
200.M. J. A. Schuetz, J. K. Brubaker, and H. G. Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367–377, 2022.
201.A. Schwarzschild, E. Borgnia, A. Gupta, F. Huang, U. Vishkin, M. Goldblum, and T. Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34:6695–6706, 2021.
202.B. Selman, H. A. Kautz, and B. Cohen. Noise strategies for improving local search. In AAAI Conference on Artifical Intelligence, volume 94, pages 337–343, 1994.
203.D. Selsam and N. Bjørner. Guiding high-performance sat solvers with unsat-core predictions. In M. Janota and I. Lynce, editors, Theory and Applications of Satisfiability Testing, pages 336–353, 2019.
204.D. Selsam, M. Lamm, B. B¨unz, P. Liang, L. de Moura, and D. L. Dill. Learning a SAT solver from single-bit supervision. In International Conference on Learning Representations, 2019.
205.S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
206.M. Shanahan, K. Nikiforou, A. Creswell, C. Kaplanis, D. G. T. Barrett, and M. Garnelo. An explicitly relational neural network architecture. In International Conference on Machine Learning, pages 8593–8603, 2020.
207.D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354–359, 2017.
208.D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of computer and system sciences, 26(3):362–391, 1983.
209.K. A. Smith. Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS Journal on Computing, 11(1):15–34, 1999.
210.W. Song, Z. Cao, J. Zhang, C. Xu, and A. Lim. Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, 109:104603, 2022.
211.A. Sperduti and A. Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(2):714–35, 1997.
212.H. Strathmann, M. Barekatain, C. Blundell, and P. Veličković. Persistent message passing. arXiv preprint, abs/2103.01043, 2021.
213.H. Sun, W. Chen, H. Li, and L. Song. Improving learning to branch via reinforcement learning. In Workshop on Learning Meets Combinatorial Algorithms, NeurIPS, 2020a.
214.L. Sun, D. Gerault, A. Benamira, and T. Peyrin. Neurogift: Using a machine learning based sat solver for cryptanalysis. In International Symposium on Cyber Security Cryptography and Machine Learning, pages 62–84, 2020b.
215.J. Suomela. Survey of local algorithms. ACM Computing Surveys, 45(2):24:1–24:40, 2013.
216.R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
217.E. D. Taillard and K. Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420–429, 2019.
218.A. Tamar, Y. Wu, G. Thomas, S. Levine, and P. Abbeel. Value iteration networks. Advances in Neural Information Processing Systems, 29:2154–2162, 2016.
219.H. Tang, Z. Huang, J. Gu, B.-L. Lu, and H. Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gnns. Advances in Neural Information Processing Systems, 33, 2020.
220.R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215–225, 1975.
221.J. Toenshoff, M. Ritzert, H. Wolf, and M. Grohe. RUN-CSP: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, abs/1909.08387, 2019.
222.P. Toth and S. Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
223.A. Trask, F. Hill, S. E. Reed, J. Rae, C. Dyer, and P. Blunsom. Neural arithmetic logic units. In Advances in Neural Information Processing Systems, pages 8035–8044, 2018.
224.C. Tucker, D. Shuffelton, R. Jhala, and S. Lerner. Opium: Optimal package install/uninstall manager. In International Conference on Software Engineering, pages 178–188, 2007.
225.P. Vaezipoor, G. Lederman, Y. Wu, C. Maddison, R. B. Grosse, S. A. Seshia, and F. Bacchus. Learning branching heuristics for propositional model counting. In AAAI Conference on Artificial Intelligence, pages 12427–12435, 2021.
226.R. van Driel, E. Demirović, and N. Yorke-Smith. Learning variable activity initialisation for lazy clause generation solvers. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings 18, pages 62–71. Springer, 2021.
227.P. J. M. Van Laarhoven and E. H. L. Aarts. Simulated annealing. In Simulated annealing: Theory and applications, pages 7–15. Springer, 1987.
228.V. V. Vazirani. Approximation Algorithms. Springer, 2010.
229.P. Veličković and C. Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273, 2021.
230.P. Veličković, L. Buesing, M. C. Overlan, R. Pascanu, O. Vinyals, and C. Blundell. Pointer graph networks. Advances in Neural Information Processing Systems, 33:2232–2244, 2020.
231.P. Veličković, A. P. Badia, D. Budden, R. Pascanu, A. Banino, M. Dashevskiy, R. Hadsell, and C. Blundell. The CLRS algorithmic reasoning benchmark. In International Conference on Machine Learning, 2022a.
232.P. Veličković, M. Bošnjak, T. Kipf, A. Lerchner, R. Hadsell, R. Pascanu, and C. Blundell. Reasoning-modulated representations. In The First Learning on Graphs Conference, 2022b.
233.P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
234.P. Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020.
235.N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8: 120388–120416, 2020.
236.O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692–2700, 2015.
237.M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolínek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
238.M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song, J. Zhou, C. Ma, L. Yu, Y. Gai, T. Xiao, T. He, G. Karypis, J. Li, and Z. Zhang. Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks. arXiv preprint, abs/1909.01315, 2019.
239.P.-W. Wang, P. Donti, B. Wilder, and Z. Kolter. SATnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pages 6545–6554, 2019.
240.B. Weisfeiler and A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12–16, 1968.
241.B. Wilder, E. Ewing, B. Dilkina, and M. Tambe. End to end learning and optimization on graphs. In Advances in Neural Information Processing Systems, pages 4674–4685, 2019.
242.R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1(2):270–280, 1989.
243.M. Winkenbach, S. Parks, and J. Noszek. Technical proceedings of the amazon last mile routing research challenge. 2021.
244.Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. arXiv preprint, abs/1901.00596, 2019.
245.A. S. Xavier and F. Qiu. MIPLearn, 2020. URL https://anl-ceeesa.github.io/MIPLearn.
246.L.-P. Xhonneux, A.-I. Deac, P. Veličković, and J. Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Processing Systems, 34:19500–19512, 2021.
247.H. Xu, K.-H. Hui, C.-W. Fu, and H. Zhang. TilinGNN: learning to tile with self-supervised graph neural network. ACM Transactions on Graphics, 39(4):129–1, 2020a.
248.K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
249.K. Xu, J. Li, M. Zhang, S. S. Du, K.-I. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020b.
250.K. Xu, M. Zhang, J. Li, S. S. Du, K.-I. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations, 2021.
251.Y. Yan, K. Swersky, D. Koutra, P. Ranganathan, and M. Hashemi. Neural execution engines. In Advances in Neural Information Processing, 2020.
252.Y. Yang and A. B. Whinston. A survey on reinforcement learning for combinatorial optimization. arXiv preprint, abs/2008.12248, 2020.
253.Y. Yang, T. Liu, Y. Wang, J. Zhou, Q. Gan, Z. Wei, Z. Zhang, Z. Huang, and D. Wipf. Graph neural networks inspired by classical iterative algorithms. In International Conference on Machine Learning, pages 11773–11783, 2021.
254.W. Yao, A. S. Bandeira, and S. Villar. Experimental performance of graph neural networks on random instances of max-cut. In Wavelets and Sparsity XVIII, volume 11138, pages 242–251. SPIE, 2019.
255.G. Yehuda, M. Gabel, and A. Schuster. It’s not what machines can learn, it’s what we cannot teach. In International Conference on Machine Learning, pages 10831–10841, 2020.
256.G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, and H. Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11975–11986, 2021.
257.R. Yolcu and B. Póczos. Learning local search heuristics for boolean satisfiability. In Advances in Neural Information Processing Systems, pages 7992–8003, 2019.
258.J. You, Z. Ying, and J. Leskovec. Design space for graph neural networks. In Advances in Neural Information Processing Systems, 2020.
259.W. Zaremba and I. Sutskever. Learning to execute. arXiv preprint, abs/1410.4615, 2014.
260.W. Zhang and T. G. Dietterich. A reinforcement learning approach to job-shop scheduling. In International Joint Conference on Artificial Intelligence, pages 1114–1120, 1995.
261.W. Zheng, D. Wang, and F. Song. OpenGraphGym: A parallel reinforcement learning framework for graph optimization problems. In International Conference on Computational Science, pages 439–452. Springer, 2020.
262.J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57–81, 2020.
263.Z. Zhu, Z. Zhang, L.-P. Xhonneux, and J. Tang. Neural Bellman-Ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476–29490, 2021.

Citation

MLA

Cappart, Q., et al. “Combinatorial Optimization and Reasoning with Graph Neural Networks”. Journal of Machine Learning Research, vol. 24, no. 130, 2023, pp. 1–1, https://www.jmlr.org/papers/v24/21-0449.html.

APA

Cappart, Q., Chételat, D., Khalil, E. B., Lodi, A., Morris, C., & Veličković, P. (2023). Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research, 24(130), 1–61. https://www.jmlr.org/papers/v24/21-0449.html

Chicago

Cappart, Q., D. Chételat, E. B. Khalil, A. Lodi, C. Morris, and P. Veličković. 2023. “Combinatorial Optimization and Reasoning with Graph Neural Networks”. Journal of Machine Learning Research 24 (130): 1–61. https://www.jmlr.org/papers/v24/21-0449.html.

Harvard

Cappart, Q. et al. (2023) “Combinatorial Optimization and Reasoning with Graph Neural Networks”, Journal of Machine Learning Research, 24(130), pp. 1–61. Available at: https://www.jmlr.org/papers/v24/21-0449.html.

Vancouver

1. Cappart Q, Chételat D, Khalil EB, Lodi A, Morris C, Veličković P (2023) Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research 24:1–61

BibTeX

@article{JMLR:v24:21-0449,
  author  = {Quentin Cappart and Didier ChÃ©telat and Elias B. Khalil and Andrea Lodi and Christopher Morris and Petar VeliÄkoviÄ},
  title   = {Combinatorial Optimization and Reasoning with Graph Neural Networks},
  journal = {Journal of Machine Learning Research},
  year    = {2023},
  volume  = {24},
  number  = {130},
  pages   = {1--61},
  url     = {http://jmlr.org/papers/v24/21-0449.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Combinatorial Optimization and Reasoning with Graph Neural Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Algorithmic Reasoning Blueprint for Combinatorial Optimization on Natural Inputs

Knowl 2 — Algorithmic Alignment of Graph Neural Networks with Dynamic Programming

Knowl 3 — Architectural and Training Prescriptions for Neural Algorithmic Reasoners

Knowl 4 — Graph Representations for General Combinatorial Optimization Frameworks

Knowl 5 — GNN-Guided Exact Solvers for Dual Bounds and Optimality Proofs

Knowl 6 — Primal Solution Paradigms for GNN-Based Combinatorial Optimization

Knowl 7 — Theoretical Expressivity and Approximation Limits of GNNs in Combinatorial Optimization

Knowl 8 — Inference Latency Overhead in GNN-Augmented Exact Solvers

Knowl 9 — Generalization, Over-smoothing, and Over-squashing Bottlenecks in GNN Optimizers

Knowl 10 — Data Generation Triviality for NP-Hard Problems Under Computational Assumptions

References

Citation

BibTeX

Access the Paper