A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation

• URL: http://arxiv.org/abs/2312.14213v2
• Date: Fri, 29 Dec 2023 03:58:45 GMT
• Title: A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation
• Authors: Haofeng Yuan, Lichang Fang, Shiji Song
• Abstract summary: 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.
• Score: 33.03891490706789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Column generation (CG) is one of the most successful approaches for solving large-scale linear programming (LP) problems. Given an LP with a prohibitively large number of variables (i.e., columns), the idea of CG is to explicitly consider only a subset of columns and iteratively add potential columns to improve the objective value. While adding the column with the most negative reduced cost can guarantee the convergence of CG, it has been shown that adding multiple columns per iteration rather than a single column can lead to faster convergence. However, it remains a challenge to design a multiple-column selection strategy to select the most promising columns from a large number of candidate columns. In this paper, we propose a novel reinforcement-learning-based (RL) multiple-column selection strategy. To the best of our knowledge, it is the first RL-based multiple-column selection strategy for CG. The effectiveness of our approach is evaluated on two sets of problems: the cutting stock problem and the graph coloring problem. Compared to several widely used single-column and multiple-column selection strategies, our RL-based multiple-column selection strategy leads to faster convergence and achieves remarkable reductions in the number of CG iterations and runtime.

Related papers

• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program [34.55787800577891]
  Column Generation (CG) is an effective and iterative algorithm to solve large-scale linear programs (LP) Previous machine-learning-based approaches for CG only add a constant quantity of columns per iteration due to the state-space explosion problem. We propose Fast Family Column Generation (FFCG) -- a novel reinforcement-learning-based CG that selects a variable number of columns as needed in an iteration.
  arXiv  Detail & Related papers  (2024-12-26T05:35:48Z)
• Machine Learning-Enhanced Ant Colony Optimization for Column Generation [5.82410475933163]
  Column generation is a powerful technique for solving optimization problems that involve a large number of variables or columns. We propose a novel method called machine learning enhanced ant colony optimization (MLACO), to efficiently generate multiple high-quality columns from a subproblem.
  arXiv  Detail & Related papers  (2024-04-23T01:00:09Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  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.
  arXiv  Detail & Related papers  (2022-06-03T03:58:54Z)
• Align then Fusion: Generalized Large-scale Multi-view Clustering with Anchor Matching Correspondences [53.09276639185084]
  Multi-view anchor graph clustering selects representative anchors to avoid full pair-wise similarities. Existing approaches do not pay sufficient attention to establishing correct correspondences between the anchor sets across views.
  arXiv  Detail & Related papers  (2022-05-30T13:07:40Z)
• 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)
• Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection [9.649210683629127]
  The problem of simultaneous column and row subset selection is addressed in this paper. An iterative approach is proposed to capture the most structural information of columns/rows via selecting a subset of actual columns/rows. We demonstrate the application of TWSP for joint channel and sensor selection in cognitive radio networks.
  arXiv  Detail & Related papers  (2021-06-13T13:16:15Z)
• Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
  We propose a novel unsupervised multi-view feature selection model based on graph learning. The contributions are threefold: (1) during the feature selection procedure, the consensus similarity graph shared by different views is learned. Experiments on various datasets demonstrate the superiority of the proposed method compared with the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-04-11T03:25:25Z)
• Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python [77.33905890197269]
  We describe a new library which implements a unified pathwise coordinate optimization for a variety of sparse learning problems. The library is coded in R++ and has user-friendly sparse experiments.
  arXiv  Detail & Related papers  (2020-06-27T02:39:24Z)

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.