A Deep Reinforcement Learning Framework For Column Generation

• URL: http://arxiv.org/abs/2206.02568v1
• Date: Fri, 3 Jun 2022 03:58:54 GMT
• Title: A Deep Reinforcement Learning Framework For Column Generation
• Authors: Cheng Chi, Amine Mohamed Aboussalah, Elias B. Khalil, Juyoung Wang, Zoha Sherkat-Masoumi
• Abstract summary: Column Generation (CG) is an iterative algorithm for solving linear programs with an extremely large number of variables (columns) We propose RLCG, the first Reinforcement Learning (RL) approach for CG. Unlike typical column selection rules which myopically select a column based on local information at each iteration, we treat CG as a sequential decision-making problem.
• Score: 13.767526395378638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Column Generation (CG) is an iterative algorithm for solving linear programs (LPs) with an extremely large number of variables (columns). CG is the workhorse for tackling large-scale integer linear programs, which rely on CG to solve LP relaxations within a branch and bound algorithm. Two canonical applications are the Cutting Stock Problem (CSP) and Vehicle Routing Problem with Time Windows (VRPTW). In VRPTW, for example, each binary variable represents the decision to include or exclude a route, of which there are exponentially many; CG incrementally grows the subset of columns being used, ultimately converging to an optimal solution. We propose RLCG, the first Reinforcement Learning (RL) approach for CG. Unlike typical column selection rules which myopically select a column based on local information at each iteration, we treat CG as a sequential decision-making problem, as the column selected in an iteration affects subsequent iterations of the algorithm. This perspective lends itself to a Deep Reinforcement Learning approach that uses Graph Neural Networks (GNNs) to represent the variable-constraint structure in the LP of interest. We perform an extensive set of experiments using the publicly available BPPLIB benchmark for CSP and Solomon benchmark for VRPTW. RLCG converges faster and reduces the number of CG iterations by 22.4% for CSP and 40.9% for VRPTW on average compared to a commonly used greedy policy.

Related papers

• Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks [24.126826148945586]
  We present a machine learning framework for optimizing the generation of Chv'atal-Gomory (CG) cuts in mixed integer linear programming (MILP) The framework trains a graph neural network to classify useful constraints for aggregation in CG cut generation. Our method closes roughly $textittwice$ as much of the integrality gap as the standard CG method while running 40$% faster.
  arXiv  Detail & Related papers  (2024-09-10T14:41:46Z)
• A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation [33.03891490706789]
  Column generation is one of the most successful approaches for solving large-scale linear programming problems. We propose a novel reinforcement-learning-based (RL) multiple-column selection strategy. Our approach is evaluated on two sets of problems: the cutting stock problem and the graph coloring problem.
  arXiv  Detail & Related papers  (2023-12-21T11:35:10Z)
• Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
  Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. Running the dualPs at the nodes of the branch-and-bound tree is computationally cumbersome due to the number of node candidates and the lack of a priori knowledge on which nodes admit useful cutting planes. We propose a novel framework based on learning to approximate the optimal value of a machineP class that determines whether a cutting plane can be generated at a node of the branch-bound tree.
  arXiv  Detail & Related papers  (2023-10-30T18:31:52Z)
• 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 Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  We generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers. Our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark.
  arXiv  Detail & Related papers  (2022-08-11T10:31:28Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  Column Generation (CG) is an effective method for solving large-scale optimization problems. We propose a Machine-Learning Pricing Heuristic that can generate many high-quality columns efficiently.
  arXiv  Detail & Related papers  (2021-12-08T03:58:25Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  Conditional gradient methods (CGM) are widely used in modern machine learning. Most efforts focus on reducing the number of iterations as a means to reduce the overall running time. We show the first algorithm, where the cost per iteration is sublinear in the number of parameters, for many fundamental optimization algorithms.
  arXiv  Detail & Related papers  (2021-11-30T05:40:14Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  State-of-the-art deep neural network (DNN) pruning techniques, applied one-shot before training starts, evaluate sparse architectures with the help of a single criterion -- called pruning score. In this work we do not concentrate on a single pruning criterion, but provide a framework for combining arbitrary GSSs to create more powerful pruning strategies.
  arXiv  Detail & Related papers  (2021-07-27T08:48:01Z)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is $straggling$ workers. Coded distributed techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. We propose a novel dynamic GC scheme, which assigns redundant data to workers to acquire the flexibility to choose from among a set of possible codes depending on the past straggling behavior.
  arXiv  Detail & Related papers  (2021-03-01T18:51:29Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  We study the conservative learning problem in the contextual linear bandit setting and introduce a novel algorithm, the Conservative Constrained LinUCB (CLUCB2) We derive regret bounds for CLUCB2 that match existing results and empirically show that it outperforms state-of-the-art conservative bandit algorithms in a number of synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-02-08T19:35:01Z)

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.