# Machine Learning-Enhanced Ant Colony Optimization for Column Generation

arXiv: https://arxiv.org/abs/2407.01546 · HTML: https://mlsanity.com/paper/2407.01546/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 39 references that are in the map.
- First posted on arXiv 23 Apr 2024.

## Builds on (most cited first, 6 of 6)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Boosting Ant Colony Optimization via Solution Prediction and Machine Learning](https://mlsanity.com/paper/2008.04213/) (2020)
- [Online Algorithms with Advice for Bin Packing and Scheduling Problems](https://mlsanity.com/paper/1311.7589/) (2013)

## Abstract (arXiv)

Column generation (CG) is a powerful technique for solving optimization problems that involve a large number of variables or columns. This technique begins by solving a smaller problem with a subset of columns and gradually generates additional columns as needed. However, the generation of columns often requires solving difficult subproblems repeatedly, which can be a bottleneck for CG. To address this challenge, we propose a novel method called machine learning enhanced ant colony optimization (MLACO), to efficiently generate multiple high-quality columns from a subproblem. Specifically, we train a ML model to predict the optimal solution of a subproblem, and then integrate this ML prediction into the probabilistic model of ACO to sample multiple high-quality columns. Our experimental results on the bin packing problem with conflicts show that the MLACO method significantly improves the performance of CG compared to several state-of-the-art methods. Furthermore, when our method is incorporated into a Branch-and-Price method, it leads to a significant reduction in solution time.