Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing

• URL: http://arxiv.org/abs/2504.02383v1
• Date: Thu, 03 Apr 2025 08:22:19 GMT
• Title: Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing
• Authors: Abdo Abouelrous, Laurens Bliek, Adriana F. Gabor, Yaoxin Wu, Yingqian Zhang,
• Abstract summary: We use Reinforcement Learning (RL) to find columns with most negative reduced cost in the Pricing Problem (PP)<n>Our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any other mechanism.<n>We show that our method solves the linear relaxation up to a reasonable objective gap within in significantly shorter running times, up to over 300 times faster for instances with 100 customers.
• Score: 5.584238928596282
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 within 9% in significantly shorter running times, up to over 300 times faster for instances with 100 customers.

Related papers

• Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application [5.584238928596282]
  Column Generation (CG) is a method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. We use a Graph neural Network (GNN) to reduce the size of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC) The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence.
  arXiv  Detail & Related papers  (2025-04-11T10:08:38Z)
• Self-Regulation and Requesting Interventions [63.5863047447313]
  We propose an offline framework that trains a "helper" policy to request interventions.<n>We score optimal intervention timing with PRMs and train the helper model on these labeled trajectories.<n>This offline approach significantly reduces costly intervention calls during training.
  arXiv  Detail & Related papers  (2025-02-07T00:06:17Z)
• All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers [0.0]
  We present a neural network-enhanced column generation (CG) approach for a parallel machine scheduling problem. By training the neural network offline and using it in inference mode to predict negative reduced costs columns, we achieve significant computational time savings. For large-sized instances, the proposed approach achieves an 80% improvement in the objective value in under 500 seconds.
  arXiv  Detail & Related papers  (2024-10-21T02:53:37Z)
• Robust Capped lp-Norm Support Vector Ordinal Regression [85.84718111830752]
  Ordinal regression is a specialized supervised problem where the labels show an inherent order. Support Vector Ordinal Regression, as an outstanding ordinal regression model, is widely used in many ordinal regression tasks. We introduce a new model, Capped $ell_p$-Norm Support Vector Ordinal Regression(CSVOR), that is robust to outliers.
  arXiv  Detail & Related papers  (2024-04-25T13:56:05Z)
• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows [0.09831489366502298]
  This paper introduces a reinforcement learning approach to optimize the Vehicle Routing Problem with Time Windows (SVRP) We develop a novel SVRP formulation that accounts for uncertain travel costs and demands, alongside specific customer time windows. An attention-based neural network trained through reinforcement learning is employed to minimize routing costs.
  arXiv  Detail & Related papers  (2024-02-15T07:35:29Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. We propose a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to enhance the performance of CG.
  arXiv  Detail & Related papers  (2023-10-15T00:05:50Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [123.55983746427572]
  We propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction.<n>A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space.
  arXiv  Detail & Related papers  (2022-02-25T16:17:23Z)
• Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
  Vehicle routing problems (VRPs) are a class of problems with wide practical applications. Previous or learning-based works achieve decent solutions on small problem instances of up to 100 customers. This article presents a novel learning-augmented local search algorithm to solve large-scale VRP.
  arXiv  Detail & Related papers  (2021-07-08T22:51:58Z)
• Model-Augmented Q-learning [112.86795579978802]
  We propose a MFRL framework that is augmented with the components of model-based RL. Specifically, we propose to estimate not only the $Q$-values but also both the transition and the reward with a shared network. We show that the proposed scheme, called Model-augmented $Q$-learning (MQL), obtains a policy-invariant solution which is identical to the solution obtained by learning with true reward.
  arXiv  Detail & Related papers  (2021-02-07T17:56:50Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  We propose a practical online method for solving a class of online distributionally robust optimization (DRO) problems. Our studies demonstrate important applications in machine learning for improving the robustness of networks.
  arXiv  Detail & Related papers  (2020-06-17T20:19:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.