論文の概要: A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation

• arxiv url: http://arxiv.org/abs/2312.14213v2
• Date: Fri, 29 Dec 2023 03:58:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-02 20:22:22.082464
• Title: A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation
• Title（参考訳）: 強化学習に基づく列生成のための複数カラム選択戦略
• Authors: Haofeng Yuan, Lichang Fang, Shiji Song
• Abstract要約: 列生成は大規模線形プログラミング問題の解決において最も成功した手法の1つである。 本稿では, 強化学習に基づく複数カラム選択戦略を提案する。 本手法は,カットストック問題とグラフカラー化問題という2つの問題に対して評価する。
• 参考スコア（独自算出の注目度）: 33.03891490706789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Column generation (CG) is one of the most successful approaches for solving large-scale linear programming (LP) problems. Given an LP with a prohibitively large number of variables (i.e., columns), the idea of CG is to explicitly consider only a subset of columns and iteratively add potential columns to improve the objective value. While adding the column with the most negative reduced cost can guarantee the convergence of CG, it has been shown that adding multiple columns per iteration rather than a single column can lead to faster convergence. However, it remains a challenge to design a multiple-column selection strategy to select the most promising columns from a large number of candidate columns. In this paper, we propose a novel reinforcement-learning-based (RL) multiple-column selection strategy. To the best of our knowledge, it is the first RL-based multiple-column selection strategy for CG. The effectiveness of our approach is evaluated on two sets of problems: the cutting stock problem and the graph coloring problem. Compared to several widely used single-column and multiple-column selection strategies, our RL-based multiple-column selection strategy leads to faster convergence and achieves remarkable reductions in the number of CG iterations and runtime.
• Abstract（参考訳）: カラム生成(CG)は、大規模線形プログラミング(LP)問題を解決する最も成功した手法の一つである。 非常に多くの変数(列)を持つLPが与えられた場合、CGの考え方は列のサブセットのみを明示的に考慮し、目的値を改善するために潜在的カラムを反復的に追加することである。 最も負のコストでカラムを追加するとcgの収束が保証されるが、単一のカラムではなく、イテレーション毎に複数のカラムを追加することがより高速な収束につながることが示されている。 しかし、多数の候補列から最も有望な列を選択するために、複数列選択戦略を設計することは依然として課題である。 本稿では,新しい強化学習ベース(RL)マルチカラム選択戦略を提案する。 私たちの知る限りでは、cgに対するrlベースの最初のマルチカラム選択戦略です。 本手法の有効性は,カットストック問題とグラフカラー問題という2つの問題に対して評価される。 RLをベースとした複数カラム選択戦略は, 広く使用されている単一カラムと複数カラムの選択戦略と比較して, より高速に収束し, CGイテレーション数や実行回数を大幅に削減する。

関連論文リスト

• Machine Learning-Enhanced Ant Colony Optimization for Column Generation [5.82410475933163]
  列生成は、多数の変数や列を含む最適化問題を解決するための強力な手法である。 サブプロブレムから複数の高品質カラムを効率よく生成する機械学習強化アリコロニー最適化(MLACO)を提案する。
  論文  参考訳（メタデータ） (2024-04-23T01:00:09Z)
• Fair Column Subset Selection [6.004035936737586]
  行列列を2つの群に分割した設定を考え,その目的は2つの群の最大誤差再構成を最小限に抑える列の部分集合を選択することである。 特定のシナリオでは、各グループごとに列を別々に選ぶことは避けられないため、期待される列数を2倍にする。 フェアセッティングのための決定論的レバレッジスコアサンプリング戦略を提案し、2つのグループが存在する場合、最小サイズのカラムサブセットのサンプリングがNPハードとなることを示す。
  論文  参考訳（メタデータ） (2023-06-07T15:00:38Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラムを解くための反復アルゴリズムである。 CGのための最初の強化学習(RL)手法であるRCCGを提案する。 各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択規則とは異なり、CGを逐次決定問題として扱う。
  論文  参考訳（メタデータ） (2022-06-03T03:58:54Z)
• Align then Fusion: Generalized Large-scale Multi-view Clustering with Anchor Matching Correspondences [53.09276639185084]
  マルチビューアンカーグラフクラスタリングは、完全なペアワイド類似性を避けるために代表アンカーを選択する。 既存のアプローチでは、ビューをまたいだアンカーセット間の正しい対応を確立するのに十分な注意を払わない。
  論文  参考訳（メタデータ） (2022-05-30T13:07:40Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection [9.649210683629127]
  本稿では,列列選択と行サブセット選択の同時選択の問題に対処する。 実際の列/行のサブセットを選択することで、列/行の最も構造的な情報をキャプチャするための反復的なアプローチが提案されている。 認知無線ネットワークにおける通信路とセンサ選択へのTWSPの適用を実証する。
  論文  参考訳（メタデータ） (2021-06-13T13:16:15Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
  グラフ学習に基づく新しい教師なしマルチビュー特徴選択モデルを提案する。 1) 特徴選択過程において, 異なる視点で共有されたコンセンサス類似度グラフが学習される。 各種データセットを用いた実験により,提案手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-04-11T03:25:25Z)
• Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python [77.33905890197269]
  本稿では,様々なスパース学習問題に対して,経路座標を統一的に最適化する新しいライブラリについて述べる。 ライブラリはR++でコード化されており、ユーザフレンドリーなスパース実験を行っている。
  論文  参考訳（メタデータ） (2020-06-27T02:39:24Z)

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

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