論文の概要: Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP

• arxiv url: http://arxiv.org/abs/2604.09556v1
• Date: Tue, 10 Feb 2026 14:17:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-19 19:09:11.491895
• Title: Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP
• Title（参考訳）: パラB&B:MIPの負荷分散決定論的並列化
• Authors: Jinyu Zhang, Di Huang, Yue Liu, Shuo Wang, Zhenyu Pu, Zhiyuan Liu,
• Abstract要約: MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。 本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。 本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
• 参考スコア（独自算出の注目度）: 50.917107318582715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables, making it widely used in production planning, logistics scheduling, and resource allocation. However, MIP remains NP-hard and cannot generally be solved to optimality in polynomial time. Branch-and-bound, a fundamental exact method, faces significant parallelization challenges due to computational heterogeneity and strict determinism requirements in commercial applications. This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver. Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads and eliminating non-deterministic synchronization primitives. A key innovation is our AI-driven load balancing mechanism employing multi-stage workload prediction models that estimate node computational complexity based on structural characteristics and historical performance data, coupled with dynamic parameter adjustment strategies. The framework executes orchestrated parallel phases including concurrent dive operations, systematic data consolidation, and intelligent node selection. Comprehensive experimental evaluation on 80 MIPLIB 2017 benchmark instances demonstrates effectiveness, achieving a geometric mean speedup of 2.17 using eight threads while maintaining complete deterministic guarantees. Performance gains become increasingly pronounced for higher node counts, with speedup factors reaching 5.12 for computationally intensive instances and thread idle rates averaging 34.7%.
• Abstract（参考訳）: MIP(Mixed-integer Programming)は、連続および整数決定変数を組み込むことで線形プログラミングを拡張し、本番計画、ロジスティクススケジューリング、リソース割り当てに広く利用されている。 しかし、MIP は NP-ハードのままであり、多項式時間で最適に解けない。 基本的な厳密な手法であるブランチ・アンド・バウンドは、計算の不均一性と商用アプリケーションにおける厳密な決定性要求により、重要な並列化課題に直面している。 本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。 本手法では,ワーカースレッド間で完全解法状態を複製し,非決定論的同期プリミティブを除去することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。 重要なイノベーションは、構造特性と過去の性能データに基づいてノードの計算複雑性を推定する多段階ワークロード予測モデルと、動的パラメータ調整戦略を組み合わせたAI駆動負荷分散機構である。 このフレームワークは、同時ダイブ操作、システマティックデータ統合、インテリジェントノード選択など、オーケストレーションされた並列フェーズを実行する。 80 MIPLIB 2017ベンチマークインスタンスに対する総合的な実験的評価は、完全な決定論的保証を維持しながら、8スレッドを使用して2.17の幾何平均スピードアップを達成することにより、有効性を示す。 高いノード数ではパフォーマンス向上が顕著になり、計算集約的なインスタンスではスピードアップ係数が5.12に達し、スレッドアイドルレートは平均34.7%に達した。

関連論文リスト

• Vectorized Online POMDP Planning [4.097364225798782]
  POMDPは部分的な可観測性問題の下での計画のためのフレームワークである。 本稿では,新たな並列オンライン解法であるVectorized Online POMDP Planner (VOPP)を提案する。 VOPPは、計画に関連するすべてのデータ構造をテンソルの集合として表現し、全ての計画ステップを完全にベクトル化された計算として実装する。
  論文  参考訳（メタデータ） (2025-10-31T05:21:39Z)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  本稿では,並列計算の理論的下界を実現する最初の非同期アルゴリズムであるリングリーダーASGDを紹介する。 我々の分析により、リングリーダーASGDは任意の勾配と時間変化速度の下で最適であることが明らかとなった。
  論文  参考訳（メタデータ） (2025-09-26T19:19:15Z)
• FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
  Mixed-Integer Linear Programming (MILP)は、複雑な意思決定問題の基本的なツールである。 混合整数線形計画法(FMIP)のための連立連続整数フローを提案する。これはMILPソリューションにおける整数変数と連続変数の共分散をモデル化する最初の生成フレームワークである。 FMIPは任意のバックボーンネットワークや様々なダウンストリームソルバと完全に互換性があり、現実世界のMILPアプリケーションにも適している。
  論文  参考訳（メタデータ） (2025-07-31T10:03:30Z)
• Pangu Embedded: An Efficient Dual-system LLM Reasoner with Metacognition [95.54406667705999]
  Pangu Embeddedは、Ascend Neural Processing Units (NPU) 上で開発された効率的なLarge Language Model (LLM) 推論器である。 既存の推論最適化 LLM でよく見られる計算コストと推論遅延の問題に対処する。 単一の統一モデルアーキテクチャ内で、迅速な応答と最先端の推論品質を提供する。
  論文  参考訳（メタデータ） (2025-05-28T14:03:02Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  大規模言語モデル(LLM)は、今日のアプリケーションでは必須であるが、推論手順は重要な計算資源を必要とする。 本稿では,多段階オンラインスケジューリング問題としてLLM推論最適化を定式化する。 我々は,アルゴリズム設計をガイドするトラクタブルなベンチマークを提供するために,流体力学近似を開発した。
  論文  参考訳（メタデータ） (2025-04-15T16:00:21Z)
• Automatic Operator-level Parallelism Planning for Distributed Deep Learning -- A Mixed-Integer Programming Approach [6.449961842220686]
  本稿では,最適性と計算効率のバランスをとる二段階のソリューションフレームワークを提案する。 我々のフレームワークは、同等または優れた性能を実現し、同じメモリ制約下で計算バブルを半分に減らします。 このような能力は、最適な並列化戦略を探求するための貴重な研究ツールであり、大規模なAIデプロイメントのための実践的な産業ソリューションである。
  論文  参考訳（メタデータ） (2025-03-12T13:00:29Z)
• aphBO-2GP-3B: A budgeted asynchronous parallel multi-acquisition functions for constrained Bayesian optimization on high-performing computing architecture [4.738678765150249]
  非同期制約付きバッチ並列ベイズ最適化法を提案する。 この方法の利点は3倍である。 aphBO-2GP-3Bフレームワークは2つの高忠実度産業応用を用いて実証されている。
  論文  参考訳（メタデータ） (2020-03-20T18:02:27Z)

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

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