論文の概要: 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の改良によりブランチ・アンド・プライス・正確な手法の性能が大幅に向上することを示した。
関連論文リスト
- 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) - An improved column-generation-based matheuristic for learning
classification trees [9.07661731728456]
決定木は機械学習(ML)における分類問題の解法として高度に解釈可能なモデルである
決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。
citefirat 2020column氏は、意思決定木を学習するためのカラムジェネレーションベースのアプローチを提案した。
論文 参考訳(メタデータ) (2023-08-22T14:43:36Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。