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 (5)

• Sequence to Sequence Learning with Neural Networks
• A Brief Survey of Deep Reinforcement Learning
• Neural Combinatorial Optimization with Reinforcement Learning
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• Message-Passing Neural Networks Learn Little's Law

Cited by in corpus (5)

• The Graph Neural Networking Challenge: A Worldwide Competition for Education in AI/ML for Networks
• Learning Hard Optimization Problems: A Data Generation Perspective
• Computing Steiner Trees using Graph Neural Networks
• Deep Learning Chromatic and Clique Numbers of Graphs
• MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization