論文の概要: FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program

• arxiv url: http://arxiv.org/abs/2412.19066v1
• Date: Thu, 26 Dec 2024 05:35:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:24:47.734674
• Title: FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program
• Title（参考訳）: FFCG:大規模線形プログラムを解くための効率良く高速な家族列生成
• Authors: Yi-Xiang Hu, Feng Wu, Shaoang Li, Yifang Zhao, Xiang-Yang Li,
• Abstract要約: カラム生成(CG)は大規模線形プログラム(LP)を効果的かつ反復的に解くアルゴリズムである CGに対する従来の機械学習ベースのアプローチは、状態空間の爆発問題のために、イテレーション毎に一定量の列を追加するだけである。 提案するFast Family Column Generation (FFCG) は,反復で必要となる列数を選択する,強化学習に基づく新しいCGである。
• 参考スコア（独自算出の注目度）: 34.55787800577891
• License:
• Abstract: Column Generation (CG) is an effective and iterative algorithm to solve large-scale linear programs (LP). During each CG iteration, new columns are added to improve the solution of the LP. Typically, CG greedily selects one column with the most negative reduced cost, which can be improved by adding more columns at once. However, selecting all columns with negative reduced costs would lead to the addition of redundant columns that do not improve the objective value. Therefore, selecting the appropriate columns to add is still an open problem and previous machine-learning-based approaches for CG only add a constant quantity of columns per iteration due to the state-space explosion problem. To address this, we propose Fast Family Column Generation (FFCG) -- a novel reinforcement-learning-based CG that selects a variable number of columns as needed in an iteration. Specifically, we formulate the column selection problem in CG as an MDP and design a reward metric that balances both the convergence speed and the number of redundant columns. In our experiments, FFCG converges faster on the common benchmarks and reduces the number of CG iterations by 77.1% for Cutting Stock Problem (CSP) and 84.8% for Vehicle Routing Problem with Time Windows (VRPTW), and a 71.4% reduction in computing time for CSP and 84.0% for VRPTW on average compared to several state-of-the-art baselines.
• Abstract（参考訳）: カラム生成(CG)は大規模線形プログラム(LP)を解くための効率的かつ反復的なアルゴリズムである。 各CGイテレーションでは、LPのソリューションを改善するために新しいカラムが追加される。 通常、CGは1つのカラムを最も負のコストで優遇的に選択するが、同時に複数のカラムを追加することで改善できる。 しかし、負のコスト削減で全てのカラムを選択すると、目的値を改善しない冗長なカラムが追加されることになる。 したがって、追加する適切な列を選択することは依然として未解決の問題であり、CGに対する従来の機械学習ベースのアプローチでは、状態空間の爆発問題のため、イテレーションあたりのカラム数が一定に限られていた。 そこで本研究では,Fast Family Column Generation (FFCG) を提案する。 具体的には,CG におけるカラム選択問題を MDP として定式化し,コンバージェンス速度と冗長列数のバランスをとる報酬計量を設計する。 我々の実験では、FFCGは一般的なベンチマークでより高速に収束し、カットストック問題(CSP)では77.1%、タイムウインドウ(VRPTW)では84.8%、CSPでは71.4%、VRPTWでは84.0%となっている。

関連論文リスト

• 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)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。 分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。 コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。 本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
  論文  参考訳（メタデータ） (2021-03-01T18:51:29Z)
• Parameter-free Locally Accelerated Conditional Gradients [91.19349793915615]
  私たちは小説を紹介します。 自由局所加速cg(pf-lacg)アルゴリズムは,厳密な収束保証を提供する。 我々の理論結果は,局所加速度を実証し,非加速アルゴリズムに対するPF-LaCGの実用的改善を示す数値実験によって補完される。
  論文  参考訳（メタデータ） (2021-02-12T22:50:01Z)
• Non-Parametric Adaptive Network Pruning [125.4414216272874]
  アルゴリズム設計を簡略化するノンパラメトリックモデリングを導入。 顔認識コミュニティに触発されて,メッセージパッシングアルゴリズムを用いて,適応的な例示数を求める。 EPrunerは「重要」フィルタを決定する際にトレーニングデータへの依存を壊します。
  論文  参考訳（メタデータ） (2021-01-20T06:18:38Z)
• Gradient Coding with Dynamic Clustering for Straggler Mitigation [57.9123881133818]
  GC-DCは、前回のイテレーションにおけるストラグラーの振る舞いに基づいて、各クラスタ内のストラグラーワーカ数を規制する。 本稿では,GC-DCが従来のGC方式に比べて通信負荷を増大させることなく,各イテレーションの平均完了時間(各イテレーション)を大幅に改善できることを数値的に示す。
  論文  参考訳（メタデータ） (2020-11-03T18:52:15Z)

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

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