論文の概要: All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers

• arxiv url: http://arxiv.org/abs/2410.15601v1
• Date: Mon, 21 Oct 2024 02:53:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:16:14.316806
• Title: All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers
• Title（参考訳）: 改善するカラム:トランスフォーマーによる並列マシンスケジューリングのためのカラム生成の強化
• Authors: Amira Hijazi, Osman Ozaltin, Reha Uzsoy,
• Abstract要約: 本稿では,並列マシンスケジューリング問題に対するニューラルネットワーク強化カラム生成(CG)アプローチを提案する。 ニューラルネットワークをオフラインでトレーニングし、推論モードで使用することにより、負の削減コスト列を予測することにより、計算時間を大幅に削減できる。 大規模インスタンスの場合,提案手法は目標値の80%を500秒未満で改善する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We present a neural network-enhanced column generation (CG) approach for a parallel machine scheduling problem. The proposed approach utilizes an encoder-decoder attention model, namely the transformer and pointer architectures, to develop job sequences with negative reduced cost and thus generate columns to add to the master problem. By training the neural network offline and using it in inference mode to predict negative reduced costs columns, we achieve significant computational time savings compared to dynamic programming (DP). Since the exact DP procedure is used to verify that no further columns with negative reduced cost can be identified at termination, the optimality guarantee of the original CG procedure is preserved. For small to medium-sized instances, our approach achieves an average 45% reduction in computation time compared to solving the subproblems with DP. Furthermore, the model generalizes not only to unseen, larger problem instances from the same probability distribution but also to instances from different probability distributions than those presented at training time. For large-sized instances, the proposed approach achieves an 80% improvement in the objective value in under 500 seconds, demonstrating both its scalability and efficiency.
• Abstract（参考訳）: 本稿では,並列マシンスケジューリング問題に対するニューラルネットワーク強化カラム生成(CG)アプローチを提案する。 提案手法は、エンコーダ・デコーダのアテンションモデル、すなわちトランスフォーマーとポインタアーキテクチャを用いて、負のコスト削減でジョブシーケンスを開発し、マスター問題に付加するカラムを生成する。 ニューラルネットワークをオフラインにトレーニングし,それを用いて負の削減コスト列を予測することによって,動的プログラミング(DP)と比較して計算時間を大幅に短縮する。 正確なDPプロシージャを使用して、マイナスコストのカラムが終了時に特定できないことを確認するため、元のCGプロシージャの最適性保証が保存される。 提案手法は,小中小のインスタンスに対して,DPを用いたサブプロブレムの解法に比べて計算時間を平均45%削減する。 さらに、このモデルは、同じ確率分布から見つからない、より大きな問題インスタンスだけでなく、トレーニング時に提示されるものとは異なる確率分布のインスタンスにも一般化される。 大規模インスタンスの場合,提案手法は目標値の80%を500秒未満で改善し,スケーラビリティと効率性を実証する。

関連論文リスト

• Optimizing the Optimal Weighted Average: Efficient Distributed Sparse Classification [50.406127962933915]
  ACOWAは、小さなランタイムの増加とともに、顕著に優れた近似品質を達成するための追加の通信を可能にする。 その結果、ACOWAは経験的リスク最小化に忠実で、他の分散アルゴリズムよりもかなり高い精度で解が得られることがわかった。
  論文  参考訳（メタデータ） (2024-06-03T19:43:06Z)
• CoRMF: Criticality-Ordered Recurrent Mean Field Ising Solver [4.364088891019632]
  我々は、RNNに基づく効率的なIsingモデル解法、Criticality-ordered Recurrent Mean Field (CoRMF)を提案する。 基礎となるIsingグラフの近似木構造を利用することで、新しく得られた臨界度順序は、変動平均場とRNNの統一を可能にする。 CoRFMはデータ/証拠のない自己学習方式でIsing問題を解き、RNNから直接サンプリングすることで推論タスクを実行することができる。
  論文  参考訳（メタデータ） (2024-03-05T16:55:06Z)
• Winner-Take-All Column Row Sampling for Memory Efficient Adaptation of Language Model [89.8764435351222]
  分散を低減した行列生成のために, WTA-CRS と呼ばれる新しい非バイアス推定系を提案する。 我々の研究は、チューニング変換器の文脈において、提案した推定器が既存のものよりも低い分散を示すという理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-05-24T15:52:08Z)
• Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization [14.732408788010313]
  MLアプリケーションはますます、複雑なディープラーニングモデルと大規模なデータセットに依存している。 計算とデータをスケールするために、これらのモデルはノードのクラスタ内で分散的にトレーニングされ、それらの更新はモデルに適用される前に集約される。 これらの設定にデータ拡張を加えることで、堅牢で効率的なアグリゲーションシステムが必要である。 この手法は,最先端のビザンツ系レジリエントアグリゲータのロバスト性を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2023-02-12T06:38:30Z)
• Using Intermediate Forward Iterates for Intermediate Generator Optimization [14.987013151525368]
  中間ジェネレータ最適化は、生成タスクのための任意の標準オートエンコーダパイプラインに組み込むことができる。 IGOの2つの密集予測タスク(viz.)、画像外挿、点雲デノイング(denoising)に対する応用を示す。
  論文  参考訳（メタデータ） (2023-02-05T08:46:15Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Highly Parallel Autoregressive Entity Linking with Discriminative Correction [51.947280241185]
  自己回帰リンクを全ての潜在的な言及に対して並列化する,非常に効率的な手法を提案する。 我々のモデルは以前の生成法より70倍高速で精度が高い。
  論文  参考訳（メタデータ） (2021-09-08T17:28:26Z)
• Partitioning sparse deep neural networks for scalable training and inference [8.282177703075453]
  最先端のディープニューラルネットワーク(DNN)には、計算とデータ管理の大幅な要件がある。 スパシフィケーション法とプルーニング法は,DNNの大量の接続を除去するのに有効であることが示されている。 その結果得られたスパースネットワークは、ディープラーニングにおけるトレーニングと推論の計算効率をさらに向上するためのユニークな課題を提示する。
  論文  参考訳（メタデータ） (2021-04-23T20:05:52Z)
• Model Fusion via Optimal Transport [64.13185244219353]
  ニューラルネットワークのための階層モデル融合アルゴリズムを提案する。 これは、不均一な非i.d.データに基づいてトレーニングされたニューラルネットワーク間での"ワンショット"な知識伝達に成功していることを示す。
  論文  参考訳（メタデータ） (2019-10-12T22:07:15Z)

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

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