論文の概要: Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring

• arxiv url: http://arxiv.org/abs/2112.04906v1
• Date: Wed, 8 Dec 2021 03:58:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-10 14:13:44.217609
• Title: Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring
• Title（参考訳）: グラフカラー化のための機械学習に基づく価格ヒューリスティックによるカラム生成の強化
• Authors: Yunzhuang Shen, Yuan Sun, Xiaodong Li, Andrew Eberhard, Andreas Ernst
• Abstract要約: カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: カラム生成(CG)は大規模最適化問題の解決に有効な手法である。 CGは、列のサブセット(変数)でサブプロブレムを解くことから始まり、徐々に現在のサブプロブレムの解を改善することができる新しいカラムを含む。 新しいカラムは、しばしばNPハードでCGアプローチのボトルネックとなる価格問題を繰り返し解決することで、必要に応じて生成される。 そこで本研究では,高品質なコラムを効率的に生成できる機械学習ベースの価格ヒューリスティック(mlph)を提案する。 CGの各イテレーションにおいて、MLPHはMLモデルを利用して価格問題の最適解を予測し、サンプリング手法を誘導して複数の高品質カラムを効率的に生成する。 グラフカラー化問題を用いて、MLPHは6つの最先端手法と比較してCGを大幅に向上し、CGの改良によりブランチ・アンド・プライス・正確な手法の性能が大幅に向上することを示した。

関連論文リスト

• All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers [0.0]
  本稿では,並列マシンスケジューリング問題に対するニューラルネットワーク強化カラム生成(CG)アプローチを提案する。 ニューラルネットワークをオフラインでトレーニングし、推論モードで使用することにより、負の削減コスト列を予測することにより、計算時間を大幅に削減できる。 大規模インスタンスの場合,提案手法は目標値の80%を500秒未満で改善する。
  論文  参考訳（メタデータ） (2024-10-21T02:53:37Z)
• Machine Learning-Enhanced Ant Colony Optimization for Column Generation [5.82410475933163]
  列生成は、多数の変数や列を含む最適化問題を解決するための強力な手法である。 サブプロブレムから複数の高品質カラムを効率よく生成する機械学習強化アリコロニー最適化(MLACO)を提案する。
  論文  参考訳（メタデータ） (2024-04-23T01:00:09Z)
• 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)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラムを解くための反復アルゴリズムである。 CGのための最初の強化学習(RL)手法であるRCCGを提案する。 各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択規則とは異なり、CGを逐次決定問題として扱う。
  論文  参考訳（メタデータ） (2022-06-03T03:58:54Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。 本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。 本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
  論文  参考訳（メタデータ） (2021-06-14T07:11:36Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• 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)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)

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

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