Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.08401 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908323124609024 |
|---|---|
| author | Abouelrous, Abdo Bliek, Laurens Gabor, Adriana F. Wu, Yaoxin Zhang, Yingqian |
| author_facet | Abouelrous, Abdo Bliek, Laurens Gabor, Adriana F. Wu, Yaoxin Zhang, Yingqian |
| contents | Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a pricing problem. For many CO problems, the pricing problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Large ESPPRC instances are difficult to solve to near-optimality. Consequently, we use a Graph neural Network (GNN) to reduces the size of the ESPPRC such that it becomes computationally tractable with standard solving techniques. Our GNN is trained by Unsupervised Learning and outputs a distribution for the arcs to be retained in the reduced PP. The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence. We apply our method on a set of Capacitated Vehicle Routing Problems with Time Windows and show significant improvements in convergence compared to simple reduction techniques from the literature. For a fixed computational budget, we improve the objective values by over 9\% for larger instances. We also analyze the performance of our CG algorithm and test the generalization of our method to different classes of instances than the training data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08401 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application Abouelrous, Abdo Bliek, Laurens Gabor, Adriana F. Wu, Yaoxin Zhang, Yingqian Machine Learning Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a pricing problem. For many CO problems, the pricing problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Large ESPPRC instances are difficult to solve to near-optimality. Consequently, we use a Graph neural Network (GNN) to reduces the size of the ESPPRC such that it becomes computationally tractable with standard solving techniques. Our GNN is trained by Unsupervised Learning and outputs a distribution for the arcs to be retained in the reduced PP. The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence. We apply our method on a set of Capacitated Vehicle Routing Problems with Time Windows and show significant improvements in convergence compared to simple reduction techniques from the literature. For a fixed computational budget, we improve the objective values by over 9\% for larger instances. We also analyze the performance of our CG algorithm and test the generalization of our method to different classes of instances than the training data. |
| title | Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2504.08401 |