Machine Learning Enhanced Ant Colony Optimization for Column Generation
- Publisher:
- Association for Computing Machinery, Inc
- Publication Type:
- Conference Proceeding
- Citation:
- GECCO 2024 - Proceedings of the 2024 Genetic and Evolutionary Computation Conference, 2024, pp. 1073-1081
- Issue Date:
- 2024-07-14
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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 sub-problem. 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.
Please use this identifier to cite or link to this item: