Machine Learning-Enhanced Ant Colony Optimization for Column Generation

• URL: http://arxiv.org/abs/2407.01546v1
• Date: Tue, 23 Apr 2024 01:00:09 GMT
• Title: Machine Learning-Enhanced Ant Colony Optimization for Column Generation
• Authors: Hongjie Xu, Yunzhuang Shen, Yuan Sun, Xiaodong Li,
• Abstract summary: 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.
• Score: 5.82410475933163
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Column generation (CG) is a powerful technique for solving optimization problems that involve a large number of variables or columns. This technique begins by solving a smaller problem with a subset of columns and gradually generates additional columns as needed. However, the generation of columns often requires solving difficult subproblems repeatedly, which can be a bottleneck for CG. To address this challenge, we propose a novel method called machine learning enhanced ant colony optimization (MLACO), to efficiently generate multiple high-quality columns from a subproblem. Specifically, we train a ML model to predict the optimal solution of a subproblem, and then integrate this ML prediction into the probabilistic model of ACO to sample multiple high-quality columns. Our experimental results on the bin packing problem with conflicts show that the MLACO method significantly improves the performance of CG compared to several state-of-the-art methods. Furthermore, when our method is incorporated into a Branch-and-Price method, it leads to a significant reduction in solution time.

Related papers

• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS) is a novel meta-heuristic method that hierarchically combines amortized inference and parallel search. Our method first leverages Generative Flow Networks (GFlowNets) to amortize a multi-modal prior distribution over a solution space.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• 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)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• 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)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• 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)
• Column $\ell_{2,0}$-norm regularized factorization model of low-rank matrix recovery and its computation [0.9281671380673306]
  This paper is concerned with the column $ell_2,0$regularized factorization model of low-rank computation problems. Numerical experiments are conducted with synthetic and real data examples.
  arXiv  Detail & Related papers  (2020-08-24T14:15:36Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

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.