Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2504.02383 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913997180108800 |
|---|---|
| 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 | In this paper, we address the problem of Column Generation (CG) using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a set of experiments where our method is compared against a Dynamic Programming (DP)-based heuristic for solving the PP, we show that our method solves the linear relaxation up to a reasonable objective gap in significantly shorter running times. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing Abouelrous, Abdo Bliek, Laurens Gabor, Adriana F. Wu, Yaoxin Zhang, Yingqian Machine Learning In this paper, we address the problem of Column Generation (CG) using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a set of experiments where our method is compared against a Dynamic Programming (DP)-based heuristic for solving the PP, we show that our method solves the linear relaxation up to a reasonable objective gap in significantly shorter running times. |
| title | Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2504.02383 |