Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking

Abstract

Existing approaches to solving combinatorial optimization problems on graphs suffer from the need to engineer each problem algorithmically, with practical problems recurring in many instances. The practical side of theoretical computer science, such as computational complexity, then needs to be addressed. Relevant developments in machine learning research on graphs are surveyed for this purpose. We organize and compare the structures involved with learning to solve combinatorial optimization problems, with a special eye on the telecommunications domain and its continuous development of live and research networks.

29 pages, 1 figure, open access journal publication

References in corpus (26)

• Statistical mechanics of complex networks
• Neural Machine Translation by Jointly Learning to Align and Translate
• Sequence to Sequence Learning with Neural Networks
• A Comprehensive Survey on Graph Neural Networks
• Playing Atari with Deep Reinforcement Learning
• A Brief Survey of Deep Reinforcement Learning
• Neural Message Passing for Quantum Chemistry
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Learning Combinatorial Optimization Algorithms over Graphs
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Neural Combinatorial Optimization with Reinforcement Learning
• Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case
• Unveiling the potential of Graph Neural Networks for network modeling and optimization in SDN
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!
• Learning a SAT Solver from Single-Bit Supervision
• Exact Algorithms for Maximum Independent Set
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Attention Models in Graphs: A Survey
• Learning Improvement Heuristics for Solving Routing Problems
• Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon
• Message-Passing Neural Networks Learn Little's Law
• The Sample-Complexity of General Reinforcement Learning
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero

Cited by in corpus (17)

• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions
• The Expressive Power of Graph Neural Networks: A Survey
• The Graph Neural Networking Challenge: A Worldwide Competition for Education in AI/ML for Networks
• Efficient Active Search for Combinatorial Optimization Problems
• Learning Hard Optimization Problems: A Data Generation Perspective
• Constructions in combinatorics via neural networks
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems
• Design of mechanisms for ensuring the execution of tasks in project planning
• Quantum-inspired optimization for wavelength assignment
• Network Calculus with Flow Prolongation -- A Feedforward FIFO Analysis enabled by ML
• DeepGANTT: A Scalable Deep Learning Scheduler for Backscatter Networks
• Computing Steiner Trees using Graph Neural Networks
• Deep Learning Chromatic and Clique Numbers of Graphs
• Adaptation and Fine-tuning with TabPFN for Travelling Salesman Problem
• MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization