論文の概要: Batched First-Order Methods for Parallel LP Solving in MIP

• arxiv url: http://arxiv.org/abs/2601.21990v1
• Date: Thu, 29 Jan 2026 17:02:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:50.023741
• Title: Batched First-Order Methods for Parallel LP Solving in MIP
• Title（参考訳）: MIPにおける並列LP解法のバッチ一階法
• Authors: Nicolas Blin, Stefano Gualandi, Christopher Maes, Andrea Lodi, Bartolomeo Stellato,
• Abstract要約: 本研究では, 線形プログラミング問題のバッチを, 強い分岐や束縛といった混合整数型プログラミング手法で効率的に解くために, 原始双対ハイブリッドアルゴリズムを拡張した。 提案手法の有効性を様々なケーススタディで検証し,計算環境に応じて一階法が従来の単純な解法より優れている問題の大きさを同定する。
• 参考スコア（独自算出の注目度）: 5.672808839120628
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present a batched first-order method for solving multiple linear programs in parallel on GPUs. Our approach extends the primal-dual hybrid gradient algorithm to efficiently solve batches of related linear programming problems that arise in mixed-integer programming techniques such as strong branching and bound tightening. By leveraging matrix-matrix operations instead of repeated matrix-vector operations, we obtain significant computational advantages on GPU architectures. We demonstrate the effectiveness of our approach on various case studies and identify the problem sizes where first-order methods outperform traditional simplex-based solvers depending on the computational environment one can use. This is a significant step for the design and development of integer programming algorithms tightly exploiting GPU capabilities where we argue that some specific operations should be allocated to GPUs and performed in full instead of using light-weight heuristic approaches on CPUs.
• Abstract（参考訳）: 本稿では,GPU上で並列に複数の線形プログラムを解くためのバッチ一階法を提案する。 提案手法は, 線形プログラミング問題のバッチを, 強い分岐や束縛といった混合整数型プログラミング手法で効率的に解くために, 原始双対ハイブリッド勾配アルゴリズムを拡張した。 行列ベクトル演算を繰り返す代わりに行列行列演算を利用することにより、GPUアーキテクチャにおいて大きな計算上の利点が得られる。 提案手法の有効性を様々なケーススタディで検証し,計算環境によって一階法が従来の単純な解法より優れている問題のサイズを同定する。 これは整数プログラミングアルゴリズムの設計と開発において重要なステップであり、GPUに特定の操作を割り当て、CPUに軽量なヒューリスティックアプローチを使わずにフルに実行するべきだ、と我々は論じている。

関連論文リスト

• Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs [38.2058847337805]
  本稿では,CPUとGPUの両方を対象とした原子再構成アルゴリズムの効率的な実装について述べる。 提案手法は,時間的複雑性を低減し,実行時間を高速化するアルゴリズムを改良した。 これらのアルゴリズムは、光学トラップの配列における中性原子の欠陥のない構成を作成するために使用できる。
  論文  参考訳（メタデータ） (2025-04-08T16:22:42Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• FastDOG: Fast Discrete Optimization on GPU [23.281726932718232]
  本稿では,構造化予測で発生する0-1整数線形プログラムを解くために,並列に並列なラグランジュ分解法を提案する。 我々の原始的アルゴリズムと双対アルゴリズムは、サブプロブレムとBDDに対する最適化の同期をほとんど必要としません。 問題に依存しない状態で、最先端の特殊アルゴリズムに近づいたり、優れていたりします。
  論文  参考訳（メタデータ） (2021-11-19T15:20:10Z)
• Efficient GPU implementation of randomized SVD and its applications [17.71779625877989]
  行列分解は、次元データの圧縮やディープラーニングアルゴリズムなど、機械学習においてユビキタスである。 行列分解の典型的な解は、計算コストと時間を大幅に増大させる複雑さを持つ。 我々は,計算行列分解の計算負担を軽減するために,現代のグラフィカル処理ユニット(GPU)で並列に動作する効率的な処理操作を利用する。
  論文  参考訳（メタデータ） (2021-10-05T07:42:41Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)

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

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