Machine Learning-Enhanced Ant Colony Optimization for Column Generation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913413389615104 |
|---|---|
| author | Xu, Hongjie Shen, Yunzhuang Sun, Yuan Li, Xiaodong |
| author_facet | Xu, Hongjie Shen, Yunzhuang Sun, Yuan Li, Xiaodong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Machine Learning-Enhanced Ant Colony Optimization for Column Generation Xu, Hongjie Shen, Yunzhuang Sun, Yuan Li, Xiaodong Neural and Evolutionary Computing Machine Learning Optimization and Control 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. |
| title | Machine Learning-Enhanced Ant Colony Optimization for Column Generation |
| topic | Neural and Evolutionary Computing Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2407.01546 |