Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |