Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring

• URL: http://arxiv.org/abs/2112.04906v1
• Date: Wed, 8 Dec 2021 03:58:25 GMT
• Title: Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring
• Authors: Yunzhuang Shen, Yuan Sun, Xiaodong Li, Andrew Eberhard, Andreas Ernst
• Abstract summary: 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.
• Score: 5.278929511653199
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a sub-problem with a subset of columns (i.e., variables) and gradually includes new columns that can improve the solution of the current subproblem. The new columns are generated as needed by repeatedly solving a pricing problem, which is often NP-hard and is a bottleneck of the CG approach. To tackle this, we propose a Machine-Learning-based Pricing Heuristic (MLPH)that can generate many high-quality columns efficiently. In each iteration of CG, our MLPH leverages an ML model to predict the optimal solution of the pricing problem, which is then used to guide a sampling method to efficiently generate multiple high-quality columns. Using the graph coloring problem, we empirically show that MLPH significantly enhancesCG as compared to six state-of-the-art methods, and the improvement in CG can lead to substantially better performance of the branch-and-price exact method.

Related papers

• 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)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  We present a Graph Diffusion-based Solution Generation (GDSG) method. This approach is designed to work with suboptimal datasets while converging to the optimal solution large probably. We build GDSG as a multi-task diffusion model utilizing a Graph Neural Network (GNN) to acquire the distribution of high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-11T11:13:43Z)
• 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)
• 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)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• 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)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems [0.0]
  We use a genetic learning method tailormade for MMOT in which the dual state within CG plays the role of an "adversary" On a sequence of benchmark problems with up to 120 gridpoints and up to 30 marginals, our method always found the exacts.
  arXiv  Detail & Related papers  (2021-03-23T15:24:50Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)

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.