論文の概要: Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling

• arxiv url: http://arxiv.org/abs/2603.28943v1
• Date: Mon, 30 Mar 2026 19:35:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:02.753851
• Title: Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling
• Title（参考訳）: 微分初期化高速化CPU-GPUハイブリッド組合せスケジューリング
• Authors: Mingju Liu, Jiaqi Yin, Alvaro Velasquez, Cunxi Yu,
• Abstract要約: 本稿では,線形計画法(ILP)として定式化されたスケジューリング問題を解くためのハイブリッドGPUフレームワークを提案する。 本稿では,従来のILPと差別化可能な最適化を組み合わせた新しい手法を提案する。具体的には,差別化可能な事前解法を用いて高品質な部分解を高速に生成し,商用ILPソルバのウォームスタートとして機能し,オープンソースのHiGHSを上昇させる。 業界規模のベンチマークによる実証的な結果は、ベースラインよりも10倍のパフォーマンス向上を示し、最適性のギャップを0.1%ドルに縮める。
• 参考スコア（独自算出の注目度）: 9.29687794194811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a hybrid CPU-GPU framework for solving combinatorial scheduling problems formulated as Integer Linear Programming (ILP). While scheduling underpins many optimization tasks in computing systems, solving these problems optimally at scale remains a long-standing challenge due to their NP-hard nature. We introduce a novel approach that combines differentiable optimization with classical ILP solving. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers (CPLEX, Gurobi) and rising open-source solver HiGHS. This method enables significantly improved early pruning compared to state-of-the-art standalone solvers. Empirical results across industry-scale benchmarks demonstrate up to a $10\times$ performance gain over baselines, narrowing the optimality gap to $<0.1\%$. This work represents the first demonstration of utilizing differentiable optimization to initialize exact ILP solvers for combinatorial scheduling, opening new opportunities to integrate machine learning infrastructure with classical exact optimization methods across broader domains.
• Abstract（参考訳）: Integer Linear Programming (ILP) として定式化された組合せスケジューリング問題を解決するためのハイブリッドCPU-GPUフレームワークを提案する。 スケジューリングは、コンピュータシステムにおける多くの最適化タスクの基盤となっているが、これらの問題を大規模に最適に解くことは、NPハードの性質のため、長年にわたる課題である。 微分可能最適化と古典的ILP解法を組み合わせた新しい手法を提案する。 具体的には,有償IPP解法 (CPLEX, Gurobi) とオープンソースの解法 HiGHS のウォームスタートとして機能する,高品質な部分解を高速に生成する。 この方法では、最先端のスタンドアロン解法と比較して、早期刈り出しを大幅に改善することができる。 業界規模のベンチマークによる実証的な結果は、ベースラインよりも10\times$パフォーマンス向上を示し、最適性のギャップを<0.1\%$に縮める。 この研究は、微分可能な最適化を利用して、組合せスケジューリングのために正確なILPソルバを初期化し、機械学習インフラストラクチャをより広い領域にわたって古典的な正確な最適化手法と統合する新たな機会を開く最初の例である。

関連論文リスト

• Efficient Optimization Accelerator Framework for Multistate Ising Problems [0.0]
  Ising MachinesはNP-Hard最適化問題を効率的に解決する新しいハードウェアアーキテクチャである。 スピン相互作用を一般化論理関数としてモデル化し,探索空間を大幅に削減する。 また,提案手法を用いてFPGA上に1024-neuronオールツーオール接続型Isingアクセラレータを設計する。
  論文  参考訳（メタデータ） (2025-05-26T17:23:47Z)
• Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems [0.0]
  本稿では,選択時の未解決学習問題の分布に最善を尽くすアルゴリズムを反復的に選択するスケジューリング手法を提案する。 我々は,BBOBテストベッド上での数値ブラックボックス最適化からよく知られた手法を実演し,従来のポートフォリオから様々な評価プロトコルにまたがって,単一と仮想のベストソルバのギャップの多くを埋める方法を示した。
  論文  参考訳（メタデータ） (2025-04-15T17:54:21Z)
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization [0.669087470775851]
  組合せ最適化問題は、産業応用において至るところに存在している。 過去数十年間、Isingタイプの問題解決ツールの開発に精力的に取り組んできた。 量子システムと古典システムの制御と操作の最近の進歩は、新しい計算パラダイムを可能にしている。
  論文  参考訳（メタデータ） (2025-03-19T17:08:55Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。 本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。 可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
  論文  参考訳（メタデータ） (2021-07-02T06:46:23Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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