Source-linked AI summary
Machine Learning-Enhanced Tabu Search for Tactical Wireless Network Design
Wissem Ahmed Zaid, Alain Hertz, Defeng Liu
TL;DR
Tactical wireless network design requires costly evaluation of many candidate moves in a constrained combinatorial search. The paper trains a GNN from Tabu Search trajectories to prioritize edge-exchange moves, and reports faster search with improved aggregate solution quality on synthetic benchmarks, while noting instance-level exceptions and a larger future search space for addition edges.
Problem
Tabu Search for tactical wireless network design is costly because many neighboring topologies require computationally expensive configuration and objective evaluation.
Method
A GNN learns from Tabu Search trajectories to classify or rank promising edge removals and guide candidate-move selection before full evaluation.
Results
TABU-ML generally achieves better average solution quality than TABU under identical stopping criteria and time limits, while reducing costly edge-exchange evaluations.
Takeaways & Limitations
Machine learning can complement a metaheuristic by guiding neighborhood exploration without modifying the objective function, feasibility conditions, or fundamental optimization components.
Takeaways & Limitations
TABU-ML does not outperform TABU on every instance, and learning to rank addition edges faces an O(n^2) candidate space compared with n −1 removable tree edges.
Abstract
from arXiv · showhide
Designing high-performance tactical wireless networks under realistic operational constraints gives rise to challenging combinatorial optimization problems, where the evaluation of candidate solutions relies on detailed physical and traffic-aware models. Although classical metaheuristics such as Tabu Search offer effective mechanisms for exploring large search spaces, their computational cost remains high because numerous candidate moves must be evaluated at every iteration. In this paper, we propose a data-driven framework that improves the efficiency of Tabu Search by learning to guide its move selection process. Rather than altering the neighborhood structure, our approach exploits the information contained in the search trajectories generated during the optimization process. At each iteration, we record both improving and non-improving edge-based transformations together with a set of descriptive features capturing the structural, geometric, and performance characteristics of the network. This information is used to train a Graph Neural Network (GNN) that predicts the impact of candidate moves on the objective function. The trained model is then integrated into the Tabu Search algorithm to rank candidate transformations according to their predicted quality, thereby reducing the number of costly objective evaluations while maintaining an effective exploration of the search space. Experimental results on synthetic benchmark instances demonstrate that the proposed learning-assisted Tabu Search notably reduces computation time while consistently producing higher-quality solutions than the standard algorithm. These findings highlight the potential of combining machine learning with metaheuristics by leveraging the implicit knowledge embedded in search trajectories, paving the way for more efficient solution methods for large-scale network design problems.
1 Introduction
Tactical wireless network design is a difficult combinatorial optimization problem because topology, connectivity, and radio-resource decisions jointly affect performance. The paper proposes using machine learning within Tabu Search to prioritize promising moves and improve search efficiency without replacing the optimization framework.
- Tactical wireless networks require coordinated decisions about the master node, topology, communication links, and radio resources.These decisions influence signal quality, interference, and effective throughput.
- Tabu Search is effective for large search spaces, but evaluating many candidate topological modifications makes neighborhood exploration computationally expensive.The paper identifies exhaustive candidate evaluation at each iteration as a central efficiency challenge.
- Machine learning guides neighborhood exploration by identifying candidate moves likely to produce high-quality solutions while preserving feasibility constraints and evaluation procedures.The learning component supports, rather than replaces, the metaheuristic.
- The proposed framework learns from search trajectories to prioritize candidate neighborhood moves before their costly evaluation.Its objective is to improve search efficiency while maintaining or enhancing solution quality.
- The paper contributes a graph-based learning model using network structure and solution-dependent features, alongside a computational study of quality and efficiency.The study analyzes the learning component's impact on solution quality, search efficiency, and performance.
2 Problem description
The problem constructs a rooted, feasible tree network and evaluates each topology through a heuristic configuration involving traffic, throughput, and radio-resource decisions. Its objective combines minimum and average effective throughput across three traffic scenarios, while topology constraints penalize infeasible designs.
- Each instance contains geographically located nodes that must be connected by a tree, with one node designated as the outward-oriented master hub.Every non-hub node has one predecessor and may have multiple successors.
- A network configuration includes antenna, channel, frequency, and point-to-point or point-to-multipoint communication choices.These choices determine how the selected topology supports communication links.
- A topology specifies connectivity, but evaluating it requires additional decisions such as hub selection, neighbor partitioning, and frequency assignment.These decisions are strongly interdependent, so one topology can admit many feasible configurations.
- The heuristic procedure produces s(T) from topology T by restricting configuration search to promising candidates, without guaranteeing optimality for that topology.The resulting solution is used as the topology's practical evaluation.
- Scenario-specific edge loads represent single-edge flows, hub-to-node communication, and bidirectional communication between node pairs.The loads are defined using descendant counts and the orientation of each edge.
- The objective maximizes a weighted combination of minimum and average effective throughput across scenarios A, B, and C.The parameter p controls the trade-off, while ω_X weights each scenario.
- Feasibility constraints limit node degrees, and any topology violating them receives objective value f(s(T)) = −∞.The master hub may have at most 20 neighbors, while other nodes may have at most 11.
- Because the configuration procedure is computationally expensive, the number of times it is invoked should be kept small.
3 Literature review
Prior work combines machine learning with graph-based optimization, exact methods, and metaheuristics, including applications to wireless networking. This paper follows the neighborhood-generation line by using a graph-based classifier to prioritize edge removals within Tabu Search rather than replacing the optimizer.
- Research on combinatorial optimization integrates learning for solution construction, evaluation, branching, move selection, and search guidance.These approaches target problems where exact methods are computationally prohibitive.
- Graph neural networks are suited to combinatorial optimization because many problems naturally represent decisions and constraints as graphs.Prior studies use graph embeddings, graph convolutions, and message passing for structured optimization decisions.
- Learning-based methods have been applied to mixed-integer programming through branching decisions learned from strong-branching information and bipartite graph representations.
- Wireless-network research applies metaheuristics and learning to topology design, routing, resource allocation, access, and other communication decisions.
- Closest prior work integrated machine learning into Tabu Search for tactical wireless network design by learning neighborhood generation.The present approach likewise uses a classifier to reduce and prioritize candidate edges for removal while retaining feasibility and Tabu Search mechanisms.
4 A Tabu Search algorithm
The baseline Tabu Search starts from a feasible tree and explores edge-exchange neighbors, selecting the best admissible move while using tabu restrictions and aspiration. Its main bottleneck is evaluating neighboring topologies through an expensive configuration procedure.
- The adopted baseline starts from a feasible tree topology and iteratively explores neighboring topologies defined by edge exchanges.The algorithm in [1] is selected because it has the best computational performance among two proposed Tabu Search algorithms.
- An edge-exchange move removes one tree edge, splits the tree, and adds a feasible edge reconnecting the resulting components.The move preserves the tree structure while changing communication paths.
- Two tabu lists prevent cycling by restricting recently added or removed edges.Ldrop forbids removing recently added edges, while Ladd forbids reinserting recently removed edges.
- A move is admissible when it is non-tabu or satisfies aspiration by improving the best solution found so far.
- At each iteration, candidate exchanges are evaluated, the best admissible neighbor becomes current, and tabu lists are updated until stopping.
- The principal bottleneck is evaluating neighboring topologies because each requires the expensive configuration procedure before its objective value can be computed.This limits the number of iterations possible within reasonable computational time.
5 A Machine learning approach for neighborhood reduction
The proposed approach uses search-trajectory data and a GNN classifier to reduce costly neighborhood evaluations in Tabu Search while preserving the baseline search procedure. It identifies promising edge removals from graph and solution features, then prioritizes those candidates during neighborhood generation.
- Motivation: O(n^3) neighboring topologies make exhaustive Tabu Search evaluation a major computational bottleneck.Each of n−1 removable edges can be paired with O(n^2) reconnection edges.
- Learning approach: A supervised classifier uses solution, graph-structure, and local-modification features to identify promising candidate edges before expensive evaluation.The approach targets edge removals whose subsequent exchanges are likely to produce high-quality neighboring topologies.
- Training data generation: Search trajectories provide labeled examples distinguishing edge removals that can lead to improving neighboring solutions from less promising removals.An edge receives a positive label when at least one feasible exchange produces a higher objective value.
- GNN model: The GNN represents solutions as graphs and combines structural, spatial, and communication features from nodes and edges.Node features include spatial coordinates and descendant counts; edge features characterize network-performance contributions.
- ML-guided Tabu Search: The GNN intervenes only in neighborhood generation by ranking candidate removals, while feasibility checks, objective evaluations, tabu restrictions, aspiration, and solution updates remain unchanged.The algorithm constructs a list of the highest-scoring candidate edges before applying the standard edge-exchange evaluation process.
6 Computational experiments
Experiments on synthetic tactical wireless-network instances compare full-neighborhood, random reduced-neighborhood, and classifier-guided Tabu Search variants. TABU-ML reduces neighborhood-evaluation effort while generally achieving stronger solution quality and more iterations than the references.
- Experimental setup: The experiments use synthetic instances with 20, 30, and 50 nodes, generated with physical radio-link parameters for evaluating signal quality, interference, and throughput.Several independently generated instances are used for each network size.
- Training data: The classifier training data comes from Tabu Search trajectories, labeling an edge positive when its removal and valid exchange produce a neighboring topology with higher objective value.The training datasets contain 926,554, 491,463, and 401,751 binary labels for 20-, 30-, and 50-node instances, respectively.
- Solution quality: TABU-ML consistently outperforms TABU-20%; average solution values rise from 30.92 to 33.34, 24.81 to 28.56, and 15.60 to 17.30 for 20-, 30-, and 50-node instances.The comparison shows that classifier-guided selection, rather than neighborhood reduction alone, accounts for the improvement.
- Solution quality: Against baseline TABU, average solution values increase from 32.80 to 33.34, 27.15 to 28.56, and 16.11 to 17.30 for 20-, 30-, and 50-node instances.TABU-ML identifies higher-quality solutions within the same time limit.
- Search efficiency: TABU-ML executes more iterations within the time limit because evaluating a smaller candidate subset reduces neighborhood exploration effort, while random reduction alone does not preserve solution quality.The learned selection retains more promising moves than random sampling.
7 Conclusion and future work
The paper integrates a learned edge-removal classifier into Tabu Search to reduce costly neighborhood evaluations while preserving the original optimization framework. Results indicate faster search and better average solution quality, while future extensions face larger search spaces for edge addition and other topology decisions.
- Learning-guided neighborhood exploration: TABU-ML uses a graph neural network classifier to select promising droppable edges before generating and evaluating the corresponding neighborhood moves.The model uses graph representations with node and edge features, and training labels derived from whether edge removal enables an improving feasible exchange.
- Learning-guided neighborhood exploration: The learning component guides neighborhood exploration without replacing feasibility checks, tabu restrictions, aspiration, reconnection evaluation, or objective computation.Its role is limited to focusing evaluation on more promising candidate moves within the existing Tabu Search procedure.
- Results: Under identical stopping criteria and time limits, TABU-ML generally achieves better average solution quality than baseline TABU.The reported gain is attributed to how neighborhood exploration is guided rather than to changes in the objective function, feasibility conditions, or core optimization components.
- Results: Reducing evaluated candidate moves makes iterations faster, allowing more iterations and more candidate topologies to be investigated within the same computational budget.The classifier therefore reallocates computation toward promising neighborhood moves.
- Results: Solution-evolution plots show that TABU-ML generally reaches competitive objective values faster than baseline TABU.The comparison tracks objective value as a function of computation time.
- Future work: Future work could guide both edge removal and edge addition, but reconnection-edge selection is harder because possible additions scale as O(n^2), versus n −1 removable tree edges.The larger addition space may require additional strategies for candidate generation and evaluation.
- Future work: Other proposed learning targets include master-hub selection, successor partitioning, antenna configuration, channel assignment, and frequency selection.These decisions interact with topology, interference, communication constraints, and achievable throughput.