PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, Magnus Boman

arXiv:2005.11081v2cs.LGcs.AIstat.ML

TL;DR

Traditional graph combinatorial optimization methods require problem-specific engineering and can be costly or unavailable for real-world problems. This survey organizes machine-learning approaches by problem setting and finds that attention- and GNN-based models often achieve near-optimal results, with some matching solver quality faster, while practical coverage remains limited.

  • Problem

    Traditional exact and approximate methods can be impractical for large real-world graph problems because of execution time, high-order polynomial complexity, or unavailable approximations.

  • Method

    The paper surveys and taxonomizes machine-learning models for graph combinatorial optimization by problem setting, comparing their performance with traditional methods and discussing networking applications.

  • Results

    Attention- and GNN-based architectures generally achieve near-optimal results, while later approaches report solver-comparable quality with greater speed and some GNNs generalize to larger instances.

  • Takeaways & Limitations

    The taxonomy helps researchers identify model classes and design aspects requiring improvement and helps practitioners choose models for their combinatorial problems.

  • Takeaways & Limitations

    Systematic evaluation of scalability, adaptability, and generalization remains essential, and network resource-management applications cover only a few machine-learning methods.

Abstract

from arXiv · show

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.

I. INTRODUCTION … II. WHY LEARN TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEMS?

The survey examines machine learning for graph-based combinatorial optimization because existing methods can be impractical and require problem-specific engineering, while such problems have broad real-world impact. It organizes recent methods, comparisons, taxonomy, and telecommunications applications, placing learned approaches alongside traditional methods and computational-complexity considerations.

  • I. INTRODUCTION: Combinatorial optimization supports routing, scheduling, planning, transportation, telecommunications, and decision-making, but existing approaches can have prohibitive execution times and require hand-engineered rules.These rules demand substantial domain knowledge and advanced theoretical expertise.
  • I. INTRODUCTION: Because many problems and datasets have graph structure, machine learning is examined as a way to overcome traditional methods’ execution-time and solution-quality limitations.The survey specifically investigates machine learning for combinatorial optimization problems on graphs.
  • A. GOAL: The survey asks whether machine learning can automate heuristic learning, identifies core methods, and assesses their applicability to practical domains.Its stated goal is to explain how machine learning can solve combinatorial optimization problems on graphs.
  • B. CONTRIBUTION: The survey introduces combinatorial optimization, reviews contemporary machine learning methods, and presents supervised and reinforcement learning approaches as a basis for analysis and comparison.These components span the survey’s introductory, methodological, and problem-specific sections.
  • B. CONTRIBUTION: A new taxonomy organized by problem setting summarizes model performance, clarifies potential and limitations, and relates learned results to traditional non-learned methods.The taxonomy also helps identify which tools are potentially useful, although the supplied passage truncates that discussion.
  • B. CONTRIBUTION: Telecommunications networks provide a rich set of combinatorial optimization problems for illustrating contemporary machine learning concepts.The survey uses networking as an application domain.
  • C. RELATED WORK: Unlike broader prior surveys, this work focuses on learning to solve combinatorial optimization problems formulated on graphs because many real-world problems are graph-defined.The survey emphasizes recent advances while distinguishing its scope from work covering general NP-hard problems or other reinforcement-learning topics.
  • II. WHY LEARN TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEMS?: Combinatorial optimization seeks efficient algorithms, yet most problems are computationally intractable, remain practically important, and require balancing theoretical complexity with useful heuristic evaluation.The section defines optimization, evaluation, and recognition formulations and notes trade-offs among time, space, and sample complexity.

A. CHALLENGES FACED BY TRADITIONAL APPROACHES · B. MOTIVATION FOR MACHINE LEARNING · III. SPECIALIZED, CONTEMPORARY MACHINE LEARNING METHODS

Traditional exact methods become prohibitively slow on large real-life problems, while machine learning is explored as a way to learn efficient, generalizable solutions without exhaustive handcrafted rules. The survey then introduces contemporary structures underlying these models, including attention mechanisms, graph neural networks, and deep reinforcement learning.

  • A. CHALLENGES FACED BY TRADITIONAL APPROACHES: Exact algorithms that enumerate all possible solutions exhibit forbidding execution times on large real-life combinatorial optimization problems.
  • A. CHALLENGES FACED BY TRADITIONAL APPROACHES: Approximate algorithms can produce near-optimal solutions and generally provide theoretical guarantees for solution quality.
  • B. MOTIVATION FOR MACHINE LEARNING: Machine learning research asks whether learning can successfully solve combinatorial optimization problems, motivated by its success on complex classification, prediction, and decision tasks.
  • B. MOTIVATION FOR MACHINE LEARNING: Vinyals et al. use supervision to learn approximate solutions to computationally intractable combinatorial optimization problems.
  • B. MOTIVATION FOR MACHINE LEARNING: Researchers pursue methods that avoid meticulously handcrafted rules, achieve high solution quality, operate quickly, and generalize to unseen graph instances from the same distribution.
  • B. MOTIVATION FOR MACHINE LEARNING: The surveyed contributions investigate machine learning as a general tool for efficiently solving combinatorial optimization problems on graphs.
  • III. SPECIALIZED, CONTEMPORARY MACHINE LEARNING METHODS: This section introduces contemporary machine learning structures underlying later models, including attention mechanisms, graph neural networks, and deep reinforcement learning.

A. ATTENTION MECHANISMS

Attention mechanisms address encoder–decoder limitations by letting the decoder use all encoder hidden states through a weighted context vector rather than only a fixed-length representation. The Transformer further replaces recurrent layers with self-attention and positional encodings to improve parallelization and long-range dependency learning.

  • Recurrent neural networks: Traditional RNNs suffer short-term memory from vanishing gradients on long sequences, motivating LSTM and GRU mechanisms.These mechanisms are used to overcome the memory limitation during backpropagation.
  • Attention mechanisms: Attention lets the decoder access any encoder hidden state instead of relying only on the encoder’s final hidden state.Bahdanau et al. introduced this approach by encoding the input as a sequence of vectors.
  • Attention mechanisms: Attention computes normalized affinities between decoder and encoder states, then weights encoder states to form a context vector for prediction and recurrent updates.The attention scores are normalized by softmax, and the context vector is concatenated with the decoder state.
  • Attention mechanisms: Attention models produce better predictions than sequence-to-sequence models by combining the context vector with the decoder state.The comparison is reported in the cited attention literature.
  • Transformers: The Transformer replaces RNNs with stacked self-attention layers and positional encodings to support parallelization and constant-cost long-range dependency computation.Its design addresses the sequential obstacle to parallelized training and the linear dependency-learning cost of attention-based sequence models.

B. GRAPH NEURAL NETWORKS

Graph neural networks process graph-structured data by exploiting meaningful relations between nodes and edges for downstream learning tasks. The section surveys recurrent, convolutional, message-passing, attention-based, and embedding-oriented graph learning approaches.

  • Graph-structured data: Graphs represent data as vertices and edges across domains including communication networks, sensor networks, urban computing, biology, and social networks.This broad applicability motivates graph-based learning methods.
  • Graph-structured data: GNNs exploit meaningful relations between graph elements to support downstream tasks such as prediction and classification.Traditional feedforward, recurrent, or convolutional networks may require simplifying assumptions to accommodate graph structure.
  • Recurrent GNNs: Recurrent GNNs initialize node embeddings randomly and apply a contractive differentiable function until convergence before sending hidden states to a read-out layer.GNN is now used as a general term for neural networks that process graph-structured data.
  • Convolutional and message-passing GNNs: GCNs aggregate each node’s features with those of its neighbors, while MPNNs generalize spatial graph convolutions as message passing through connecting edges.Unlike recurrent GNNs, GCNs use stacked convolutional layers with separate weights; node representations can feed an output or graph-level read-out.
  • Attention and graph embeddings: Attention mechanisms improve GNNs by focusing on the most relevant task-related information, and graph embeddings preserve graph structure and node content in low-dimensional vectors.Attention-based models can support inductive learning on unseen graph instances, while embeddings facilitate classification, clustering, and recommendation.

C. (DEEP) REINFORCEMENT LEARNING

Reinforcement learning learns through interaction with an uncertain environment to maximize rewards, using policies, value functions, and optionally environment models. For graph combinatorial optimization, the surveyed approaches span tabular and approximate methods, including Q-learning, policy gradients, and actor-critic techniques.

  • Foundations: Reinforcement learning learns from interaction with an uncertain environment to maximize a reward function, unlike supervised learning from labeled data or unsupervised pattern discovery.Its four basic elements are a policy, reward signal, value function, and optionally a model of the environment.
  • Solution methods: Reinforcement learning methods divide into tabular approaches for small state-action spaces and approximate approaches for arbitrary large state spaces.Tabular methods can often find the exact optimal solution and policy, whereas approximate solutions are preferred when optimal policies are impractical to find.
  • Value-based methods: Q-learning estimates the optimal action-value function by iteratively constructing a Q-table containing possible state-action combinations.Experience replay buffers store past sequential experiences and randomly sample them during training to reduce temporal correlations.
  • Policy-based methods: REINFORCE is an approximate policy-gradient method that directly improves a parameterized policy using the gradient of a scalar performance measure.Its iterations run the policy, calculate the objective gradient, and update the policy parameters.
  • Actor-critic methods: Actor-critic methods combine value-based and policy-based reinforcement learning by estimating cumulative rewards while optimizing a parameterized strategy.A3C uses asynchronous gradient descent across parallel environment instances, reducing experience correlation and avoiding the replay buffer required by DQN and related methods.

IV. LEARNING TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEMS ON GRAPHS

The survey categorizes machine-learning models for graph-based combinatorial optimization first by learning structure, then by supervised or reinforcement learning. It presents this categorization alongside surveyed problems, contributions, and the contemporary research timespan.

  • The categorization first distinguishes attention mechanisms, GNNs, and their variants as learning structures.Within each category, contributions are further differentiated by supervised or reinforcement learning, with chronology followed where possible.
  • The survey organizes contributions according to learning structure and machine-learning approach.The organization is designed to compare contemporary methods for solving combinatorial optimization problems on graphs.
  • Figure 1 depicts the categorization together with surveyed problems, contributions, and the timespan of contemporary research.

A. ATTENTION MECHANISMS: POINTER NETWORKS AND TRANSFORMER ARCHITECTURE · 1) Supervised learning · 2) Reinforcement learning

The section traces attention-based methods from supervised pointer networks, which select input positions for variable-length outputs, to reinforcement-learning and Transformer-based approaches that reduce reliance on labels and extend applicability to broader optimization settings. It also highlights limitations involving fixed output lengths, training data, dynamic systems, and constructive solution quality.

  • 1) Supervised learning: The pointer-network framework removes the fixed output-length limitation of earlier sequence-to-sequence attention models, enabling variable-length outputs tied to input size.Earlier sequence-to-sequence models require the output length to be fixed a priori and therefore cannot handle outputs varying with input length.
  • 1) Supervised learning: Pointer networks use attention to select input positions as discrete outputs, addressing problems whose output length depends on the input length.They replace attention-based context-vector blending with pointers to input elements, whose softmax scores form a probability distribution.
  • 1) Supervised learning: Vinyals et al. apply supervised pointer networks to planar convex hulls, Delaunay triangulations, and planar 2D Euclidean TSP, reporting improved performance over sequence-to-sequence and attention architectures.The three geometric optimization problems were solved with labeled data and without hyper-parameter tuning.
  • 2) Reinforcement learning: Bello et al. replace labeled training with model-free policy-based reinforcement learning for TSP, using expected tour length as the reward signal in an actor-critic approach.The pointer network sequentially predicts the next tour node while its parameters are optimized through policy gradients.
  • 2) Reinforcement learning: Active search starts from a random policy, iteratively optimizes pointer-network parameters, and retains the best solution found during search.Decoding can greedily select the highest-probability node or explore sampled candidate tours and choose the shortest.
  • 2) Reinforcement learning: Reinforcement-learning attention models extend beyond basic static TSP toward dynamic VRP, permutation-invariant TSP and VRP variants, and hierarchical constrained optimization.The surveyed approaches also expose a limitation: Bello et al.’s model is designed for static problems, whereas Nazari et al. adapt it to dynamic settings.
  • 2) Reinforcement learning: Transformer encoders combined with REINFORCE and 2-opt heuristics produce TSP results closer to optimality than Bello et al.’s model by combining learned and traditional heuristics.Deudon et al. replace the recurrent encoder with a Transformer based solely on multi-head attention.
  • 2) Reinforcement learning: Learning incremental construction heuristics can be suboptimal because sampling multiple solutions still generates them with the same constructive heuristic.Wu et al. question whether repeatedly adding one node at each step can adequately improve solution quality.

B. GRAPH NEURAL NETWORKS

Graph neural networks are used across supervised and reinforcement-learning frameworks to solve diverse graph combinatorial optimization problems. These methods learn node, edge, or graph representations and construct, classify, or predict solutions through message passing, Q-learning, search, or self-play.

  • Supervised learning: Supervised GCNs estimate node participation in optimal solutions for SAT, MIS, MVC, and MC, using specialized structures and losses to distinguish multiple solutions.The framework identifies potential solution nodes and passes them to a neural network that predicts the solution set.
  • Supervised learning: Mittal et al. extend supervised GCN-based learning to influence maximization, MVC, and MCP on billion-size graphs through node embeddings and a Q-function.The two-phase framework first learns individual node embeddings, then predicts the solution set with a deep neural network.
  • Reinforcement learning: A common reinforcement-learning approach incrementally adds nodes to a solution using graph embeddings and Q-learning, but this can generalize poorly across all possible graphs.Barret et al. propose an alternative exploration approach because a single function approximation may be suboptimal.
  • Graph neural network applications: For TSP, GNNs predict edge probabilities or exchange messages between embedded nodes and edges, while greedy and beam-search procedures convert predictions into valid tours.Beam search explores limited-width alternatives and can expand partial tours until all graph nodes are visited.
  • Graph neural network applications: Message-passing GNNs also classify graph properties, including TSP decision feasibility, graph colorability, and SAT satisfiability, using iterative node and edge representations.SAT is encoded as a graph connecting literal and clause nodes, while graph coloring additionally uses global graph embeddings for each color.
  • Reinforcement learning: Abe et al. retain reinforcement learning for combinatorial optimization but replace Q-learning with an extended AlphaGo Zero approach trained through self-play.Their method follows Dai et al.’s reinforcement-learning architecture while alternating simulation and play.

V. PERFORMANCE · A. TRAVELLING SALESMAN PROBLEM

The performance survey organizes graph-based machine-learning approaches to compare methods, evaluation settings, advantages, and deficiencies without designating a universally best performer. For TSP, learned models increasingly improve scalability and solution quality, but generalization, supervision, runtime, and optimality remain trade-offs.

  • V. PERFORMANCE: The performance taxonomy organizes surveyed graph optimization methods to compare approaches, evaluation settings, advantages, and deficiencies, while avoiding a universal best-performer ranking.The appropriate choice depends on the objective and problem instance.
  • V. PERFORMANCE: Big O complexity is explicitly evaluated for only Dai et al., whose architecture has polynomial O(k|E|), k ≤|V | time-complexity.The survey separately references complexity analyses for attention models, recurrent GNNs, GCNs, graph autoencoders, and reinforcement learning, including sample-complexity.
  • A. TRAVELLING SALESMAN PROBLEM: Vinyals et al. show supervised pointer networks can approximate TSP solutions, but the model does not generalize to larger instances and requires exact or approximate supervision.Training uses exact solutions for n ≤ 20 and approximate solutions for larger graphs.
  • A. TRAVELLING SALESMAN PROBLEM: Bello et al.’s reinforcement-trained pointer network surpasses Vinyals et al.’s supervised model, but remains inferior to Concorde while greedy RL pretraining is much faster than the solver.Training and testing use graphs with n = {20, 50, 100} nodes.
  • A. TRAVELLING SALESMAN PROBLEM: Deudon et al.’s hybrid heuristic outperforms Bello et al.’s framework across tested graph sizes, with runtime worse than Google OR-Tools VRP, close to Concorde, and significantly better than Bello et al.The framework is trained on n = {20, 50} and also tested on n = 100.
  • A. TRAVELLING SALESMAN PROBLEM: For graphs up to n = 300 under matched training and testing distributions, S2V-DQN achieves R(SI, PI) ∈[1, 1.1)) and outperforms Bello et al. and most considered baselines.Dai et al. use an approximation ratio comparing the obtained solution with the best known solution.
  • A. TRAVELLING SALESMAN PROBLEM: Kool et al. obtain smaller optimality gaps than several prior models and heuristics, but the performance gap increases when generalizing to instances up to n = 125.Ma et al. are less optimal than Kool et al. on n = {20, 50}, while adding local 2-opt improves their approximate gap beyond Dai et al.’s reported result.
  • A. TRAVELLING SALESMAN PROBLEM: TSP approaches retain important limitations: Wu et al.’s learned 2-opt policy generalizes across initial solutions, whereas Nowak et al. require expensive ground truth and imitate a heuristic rather than directly optimizing cost.Joshi et al.’s greedy GCN has smaller gaps than,, and for n = {20, 50} but a larger gap for n = 100; beam search makes it faster than Kool et al., while the shortest-path heuristic increases evaluation time.

B. VEHICULAR ROUTING PROBLEM

Learned attention and reinforcement-learning methods address multiple vehicular routing problems while adapting across problem settings. Nazari et al.’s method also outperforms Google OR-Tools on roughly 61% of tested capacitated VRP instances and is suggested to be robust to problem changes.

  • B. VEHICULAR ROUTING PROBLEM: Nazari et al.’s reinforcement-learning method outputs shorter tours than Google OR-Tools in roughly 61% of capacitated VRP cases with n = {50, 100} customers.Google OR-Tools is described as among the best open-source VRP solvers according to Nazari et al.
  • B. VEHICULAR ROUTING PROBLEM: Nazari et al. suggest their model is robust to changes in customer demand or location because it can automatically adapt.The passage presents this as an author-suggested property of the model.
  • B. VEHICULAR ROUTING PROBLEM: Kool et al. use attention mechanisms and reinforcement learning to solve TSP, VRP, and several VRP variants.The approach is applied across routing problems with different objectives and constraints.
  • B. VEHICULAR ROUTING PROBLEM: The model’s use across four different routing problems demonstrates adaptability to different problem settings.This versatility avoids devising new heuristics for each possible problem modality.

C. MAXIMUM CUT … F. MAXIMUM COVERAGE PROBLEM

Across maximum cut, vertex cover, independent set, clique, and coverage problems, graph-learning methods achieve near-optimal or superior solutions, generalize beyond training sizes, and sometimes improve speed through alternative search mechanisms.

  • C. MAXIMUM CUT: S2V-DQN achieves near-optimal MaxCut solutions on Barabási-Albert graphs and generalizes to instances with 1,000–1,200 nodes.For training and testing, node counts range from 200–300; optimal solutions are produced by CPLEX.
  • C. MAXIMUM CUT: Barrett et al.’s MaxCut improvements arise from reversible decisions, suitable observations and rewards, heuristic flexibility, and selecting the best result across episodes.Their evaluation uses S2V-DQN as a baseline on Barabási-Albert and Erdős-Rényi graphs.
  • C. MAXIMUM CUT: Abe et al.’s AlphaGo Zero-inspired MaxCut model generally outperforms S2V-DQN on synthetic and real-world data, at the cost of greater computation and longer training.Training uses Erdős-Rényi graphs with n = [40, 50], while testing includes Network Repository datasets.
  • D. MINIMUM VERTEX COVER: For MVC, S2V-DQN reaches practically optimal ratios on graphs with n ≤500 and averages R(SI, PI) = 1.0062 on 1,000–1,200-node graphs.Training and testing graph sizes extend up to [400, 500].
  • D. MINIMUM VERTEX COVER: MVC models obtain optimal solutions comparable to heuristic solvers, generalize across datasets and much larger instances, and can scale toward billion-size networks.Mittal et al.’s model outperforms S2V-DQN on Barabási-Albert graphs with at most 500k nodes and is reported as orders of magnitude faster.
  • E. MAXIMAL INDEPENDENT SET AND MAXIMAL CLIQUE: Li et al.’s model finds 100% of tested MIS solutions and achieves the best reported results on SNAP, citation-network, and BUAA-MC datasets.The model is trained on SATLIB and tested on MIS problems from SATLIB and the SAT Competition.
  • E. MAXIMAL INDEPENDENT SET AND MAXIMAL CLIQUE: Abe et al. report that their MC results exceed S2V-DQN, while MIS performance varies across GNN implementations and instances.Training uses Erdős-Rényi graphs with n = [80, 100], followed by synthetic and real-world testing.
  • F. MAXIMUM COVERAGE PROBLEM: For maximum coverage, Mittal et al.’s model outperforms S2V-DQN and GCN with three search and is four to five times faster than Li et al.’s approach.The reported speed-up is attributed to one GNN call and Q-learning prediction instead of tree search.

G. SATISFIABILITY · H. GRAPH COLORING · I. DISCUSSION

The surveyed methods include neural approaches to SAT and graph coloring, while the discussion identifies attention and GNNs as prominent structures for capturing graph relations. Practical deployment depends on scalability, adaptability, generalization, execution time, and automation, supported by abundant recurring problem data.

  • G. SATISFIABILITY: Neuro SAT does not achieve competitive results against specialized solvers in the surveyed comparison.Training uses paired random SAT instances differing by negating one literal occurrence in one clause.
  • H. GRAPH COLORING: 82% accuracy was achieved by a GNN trained on graphs with 40–60 nodes and 3–7 colors, while testing scaled to an instance with 561 nodes.The model generalized to unseen larger graph-coloring instances.
  • I. DISCUSSION: Attention mechanisms and GNNs are prominent structures because they capture relevant context and inherent graph structure through node relations.Both approaches target the complex relations between graph nodes.
  • I. DISCUSSION: Problem structure and abundant data from recurring practical applications enable machine learning, while reducing dependence on deep domain expertise is a primary ambition.The same problems repeatedly emerge across practical fields, making data availability often vast.
  • I. DISCUSSION: Practical machine-learning models must address scalability, adaptability, generalization, execution time, and automation before overcoming current tools’ limitations.These challenges are identified as prerequisites for practical applicability.
  • I. DISCUSSION: Scalability remains difficult because solution quality often drops quickly when graph instances increase slightly, despite some models scaling to much larger instances.The desired behavior is maintaining observed quality for larger problems from the same data-generating function.
  • I. DISCUSSION: Adaptability requires handling changed problem settings or related tasks without redesigning and reoptimizing algorithms, while generalization requires strong performance on unseen instances without complete retraining.The surveyed literature includes examples of adaptation to problem changes and solving multiple related tasks.
  • I. DISCUSSION: Recent work increasingly seeks generalization and solver-comparable quality at greater speed, while practical automation should scale, adapt, generalize, and improve without manual intervention.Execution-time examples achieve performance close to optimal solvers but significantly faster; combining machine learning with traditional methods may further improve design and performance.

VI. NETWORKING APPLICATIONS … B. SCHEDULING

The survey examines machine-learning approaches for combinatorial optimization in networking, emphasizing resource management, network modeling, routing, and scheduling. It presents representative applications while noting that the coverage is not exhaustive.

  • VI. NETWORKING APPLICATIONS: Large-scale communication networks need automated operations and resource management that balance conflicting objectives, including energy-efficient delivery of low-latency services.
  • VI. NETWORKING APPLICATIONS: The networking survey assesses machine learning for complex resource-management problems through representative instances and combinations of methods introduced earlier.
  • VI. NETWORKING APPLICATIONS: The discussed contributions are illustrative rather than exhaustive analyses of machine learning applied to networking resource-management problems.
  • A. ROUTING: Routing is a constrained resource-allocation problem involving selection of paths between sources and destinations, with applications across domains including communication networks.
  • 1) Network modeling: Conventional analytical network models rely on simplifying assumptions about arrivals and queueing, limiting their practical applicability to heterogeneous, large-scale communication systems.
  • 1) Network modeling: An adapted MPNN models bidirectional interactions between paths and links, using summation for path aggregation and RNN-based aggregation for sequential link dependence.
  • 1) Network modeling: Training solely on the 14-node NSFNet topology, the model generalized to Geant2 and GBN, although delay and jitter prediction accuracy decreased on unseen and larger topologies.
  • B. SCHEDULING: Scheduling maps work-elements to resource instances and determines their processing order to achieve a high-level objective, with representative networking approaches summarized in Table 5.

1) Cluster Job Scheduling … 1) Virtual Network Function Orchestration

The survey presents graph-based learning approaches for scheduling jobs, edge content, and packets under complex resource and network conditions. It also covers resource allocation for VNFs, emphasizing dynamic adaptation, scalability, and generalization challenges.

  • 1) Cluster Job Scheduling: Cluster schedulers assign DAG job stages to executors while scaling across thousands of jobs and hundreds of machines.Jobs contain processing stages and tasks connected by input-output dependencies.
  • 1) Cluster Job Scheduling: Decima reduces average job completion time by at least 21% under average load and 200% under high load versus optimized weighted fair scheduling.It also outperforms schemes such as Graphene by at least 30% for CPU and memory scheduling.
  • 2) Edge-Layer Content Scheduling: Edge-layer scheduling must serve heterogeneous applications and queues sharing resources across clients, devices, and varying channel conditions.Its complexity grows with the number of clients, queues per device, and edge devices.
  • 2) Edge-Layer Content Scheduling: DeepCast uses reinforcement learning and an A3C network to schedule and transcode crowdcast content using real-time network information for personalized QoE.The framework accommodates diverse viewer preferences, including channel-switching latency and fidelity sensitivity.
  • 3) Packet Scheduling: Packet scheduling distributes packets across known multipath subflows despite heterogeneous delay and capacity, which can require receiver buffering for reordering.Reinforcement learning is used to adapt scheduling to dynamic heterogeneous network environments.
  • C. RESOURCE ALLOCATION: Resource allocation provisions memory, CPU, or bandwidth before scheduling to fulfill application requirements.The survey summarizes representative networking approaches in a dedicated overview table.
  • 1) Virtual Network Function Orchestration: VNF orchestration separates network functions from hardware, supports scaling, and chains sequential VNFs into service function chains.VNFs may be instantiated across virtual machines, with one machine per component, and scaled horizontally or vertically.
  • 1) Virtual Network Function Orchestration: Mijumbi et al. target autonomous dynamic VNF resource allocation using SFC topology, while identifying test accuracy, traffic arrivals, and larger-SFC memory limits as open issues.The approach addresses changing load on individual VNFs rather than only VNF placement.

2) Network Slicing … VII. SUMMARY AND OUTLOOK

The survey presents machine-learning approaches for network resource-management problems, highlighting gains over baselines while emphasizing scalability, generalization, execution time, and the need to broaden evaluated methods. It concludes that learning-based methods can help automate efficient solutions to recurrent combinatorial optimization problems on graphs.

  • 2) Network Slicing: EdgeSlice uses decentralized deep reinforcement learning with distributed agents and centralized coordination for multi-resource allocation across wireless edge-computing slices.The evaluation considers mobile application offloading across two slices with different frame resolutions and compares EdgeSlice with traffic-aware orchestration and EdgeSlice-NT.
  • 2) Network Slicing: 3.69x and 2.74x improvements in system performance are obtained by EdgeSlice over its comparison approaches for slice-dependent metrics.The compared methods are traffic-aware resource orchestration and EdgeSlice-NT, which omits slice queue length from the state description.
  • 3) Computing Resources in Wireless Networks: The dynamic fog-computing resource-allocation problem is formulated as NP-hard and addressed with a deep Q-network that accounts for changing node conditions.The approach targets online allocation under mobility and workload variations, which existing approaches reportedly ignore or address in cloud settings.
  • D. DISCUSSION: Machine-learning approaches generally outperform baseline approaches on optimal performance, while scalability, adaptability, and generalization over unseen inputs receive varying attention.The survey identifies scalability and generalization as especially emphasized design criteria.
  • D. DISCUSSION: GNNs dominate the surveyed work, followed by deep reinforcement learning, with GNNs viewed as key enablers of scalability in networking.The authors relate reinforcement learning to networks as discrete event systems and qualify the surveyed list as non-exhaustive.
  • D. DISCUSSION: Machine-learning algorithms are not clearly faster than baseline heuristics or solvers, although many can be parallelized when practical conditions require it.Execution time depends on problem size and data volume.
  • VII. SUMMARY AND OUTLOOK: The survey finds that machine learning can support efficient, automated solutions to recurrent graph-based combinatorial optimization problems, while broader evaluation of methods remains needed.The illustrative network resource-management studies cover only a limited set of methods compared with approaches available in other domains.

APPENDIX. COMBINATORIAL OPTIMIZATION PROBLEMS ON GRAPHS

The appendix defines several graph and combinatorial optimization problems through their feasible structures and objectives, including routing, partitioning, covering, selection, coloring, satisfiability, and packing. It also notes applications and selected exact, heuristic, or complexity results for these problems.

  • TSP: TSP seeks a minimum-cost Hamiltonian cycle visiting every city once and returning to the start, with applications including transportation, communications, scheduling, planning, microchip design, and DNA sequencing.Dynamic programming solves TSP in O(|V|22|V|) time.
  • VRP: VRP extends TSP by minimizing tour cost while satisfying constraints such as vehicle capacity and single-vehicle visits.Tour cost may represent route length, time, or number of vehicles.
  • Cut and covering problems: MaxCut maximizes the weight crossing a vertex partition, while MVC finds the smallest vertex subset incident to every edge.MaxCut has applications in protein folding, portfolio optimization, and physics; MVC arises in biochemistry and biology.
  • Clique and independence problems: MC finds the largest complete vertex subset, whereas MIS finds the largest subset containing no adjacent vertices.MC appears in clustering and bioinformatics, while MIS supports classification, coding theory, geometry, and VLSI design.
  • Coverage problems: MCP selects at most k sets, or b nodes in a bipartite formulation, to maximize covered elements or neighboring nodes.The appendix cites heuristic and metaheuristic approaches for MCP.
  • Coloring and packing problems: Graph Coloring minimizes colors subject to adjacent nodes receiving different colors, while KP maximizes profit under a weight capacity; both support resource-allocation applications.Coloring is used in planning, scheduling, and allocation; knapsack models radio resources and packet transmission in wireless networks.
Loading 2005.11081v2…