Integrating Algorithmic Insights into Artificial Intelligence Techniques for Solving Combinatorial Optimisation Problems

Combinatorial optimization (CO), essential in urban planning, logistics, and telecommunications fields, involves finding optimal solutions among vast possibilities. However, as problem complexity grows, traditional optimization methods struggle to deliver solutions efficiently. Recently, artificial intelligence (AI) has shown promise in addressing this challenge by leveraging past problem-solving experiences. AI techniques can learn patterns and predictions from large datasets, guiding optimization algorithms toward more efficient solution exploration. This integration of CO and AI offers the potential to improve solution quality and accelerate problem-solving for real-world applications previously considered intractable. AI approaches like deep learning, graph neural networks, and reinforcement learning have been applied to CO problems end-to-end. However, these methods often struggle to generalize across varying instance sizes or distributions. Bengio et al. recently emphasized the need to incorporate algorithmic insights into AI to overcome these limitations. Despite progress in this area, achieving effective integration remains a significant challenge. This thesis investigates techniques to integrate algorithmic insights into AI for solving larger and more complex CO problems. First, we propose using approximation algorithm insights as features in a lightweight supervised learning framework called Learning-to-Prune. Here, a supervised classification model predicts variable values to reduce the search space, with the pruned instance solved by an exact algorithm. This approach effectively addresses problems like set cover, facility location, k-median, and max coverage, achieving superior optimality-runtime trade-offs compared to commercial ILP solvers. Furthermore, our method generalizes well to larger problem instances.

Next, we extend the Learning-to-Prune framework to the minimum Steiner tree problem in graphs. Our framework computes near-optimal solutions significantly faster than commercial ILP solvers. When solutions are suboptimal, they can often be improved through lightweight local search or as a warm start for an ILP solver. These results underscore the versatility of the framework in addressing diverse CO problems.

Finally, we explore the Rosenthal potential function, a concept from algorithmic theory, to solve weighted set cover problems. This function, previously used in local search-based approximation algorithms, is incorporated into a new genetic algorithm. By designing tailored selection, mutation, and crossover operators, our genetic algorithm achieves near-optimal solutions on many benchmark instances, outperforming existing genetic algorithms and ILP solvers in optimality-runtime trade-offs. An ablation study confirms the critical role of the Rosenthal potential function in these improvements.