論文の概要: Machine Learning-Enhanced Ant Colony Optimization for Column Generation

• arxiv url: http://arxiv.org/abs/2407.01546v1
• Date: Tue, 23 Apr 2024 01:00:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-22 22:28:39.837652
• Title: Machine Learning-Enhanced Ant Colony Optimization for Column Generation
• Title（参考訳）: 機械学習による列生成のためのアントコロニー最適化
• Authors: Hongjie Xu, Yunzhuang Shen, Yuan Sun, Xiaodong Li,
• Abstract要約: 列生成は、多数の変数や列を含む最適化問題を解決するための強力な手法である。 サブプロブレムから複数の高品質カラムを効率よく生成する機械学習強化アリコロニー最適化(MLACO)を提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: カラム生成(CG)は、多数の変数や列を含む最適化問題を解くための強力な手法である。 このテクニックは、列のサブセットで小さな問題を解くことから始まり、必要に応じて徐々に追加の列を生成する。 しかし、カラムの生成は、しばしば難解なサブプロブレムを何度も解決する必要があるため、CGのボトルネックになりうる。 この課題に対処するために、サブプロブレムから複数の高品質カラムを効率的に生成する機械学習強化アリコロニー最適化(MLACO)を提案する。 具体的には、サブプロブレムの最適解を予測するためにMLモデルをトレーニングし、このML予測をACOの確率モデルに統合し、複数の高品質カラムをサンプリングする。 MLACO法はいくつかの最先端手法と比較してCGの性能を著しく向上させることが示された。 さらに,本手法をブランチ・アンド・プライス法に組み込むと,解時間を大幅に短縮する。

関連論文リスト

• A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation [33.03891490706789]
  列生成は大規模線形プログラミング問題の解決において最も成功した手法の1つである。 本稿では, 強化学習に基づく複数カラム選択戦略を提案する。 本手法は,カットストック問題とグラフカラー化問題という2つの問題に対して評価する。
  論文  参考訳（メタデータ） (2023-12-21T11:35:10Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Truncated Matrix Power Iteration for Differentiable DAG Learning [47.69479930501961]
  本稿では,列ベースDAG制約を近似するために,効率的な乱数行列パワーを持つ新しいDAG学習法を提案する。 実験により,DAG学習法は,様々な設定で従来の最先端技術よりも優れていた。
  論文  参考訳（メタデータ） (2022-08-30T23:56:12Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems [0.0]
  CG内の二重状態が「逆」の役割を果たすMMOT用に作られた遺伝的学習法を使用します。 最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に精度を見出した。
  論文  参考訳（メタデータ） (2021-03-23T15:24:50Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• Column $\ell_{2,0}$-norm regularized factorization model of low-rank matrix recovery and its computation [0.9281671380673306]
  本稿では低ランク計算問題の列 $ell_2,0$regularized factorization モデルについて述べる。 数値実験は、合成および実データ例を用いて行われる。
  論文  参考訳（メタデータ） (2020-08-24T14:15:36Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。