論文の概要: Learning to Configure Separators in Branch-and-Cut

• arxiv url: http://arxiv.org/abs/2311.05650v1
• Date: Wed, 8 Nov 2023 01:50:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-13 16:58:18.331237
• Title: Learning to Configure Separators in Branch-and-Cut
• Title（参考訳）: ブランチ・アンド・カットにおけるセパレータ構成の学習
• Authors: Sirui Li, Wenbin Ouyang, Max B. Paulus, Cathy Wu
• Abstract要約: 混合整数線形プログラム(MILP)の解法における切削平面の重要性 現代のMILPソルバは、様々な分離器を頼りに、解法プロセス中に分離器を頻繁に呼び出すことによって、様々な切断面を生成する。 本研究は, セパレータを適切に選択することでMILPソルバを劇的に高速化できることを示す。
• 参考スコア（独自算出の注目度）: 10.59342979240623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of cutting planes by invoking the separators frequently during the solving process. This work identifies that MILP solvers can be drastically accelerated by appropriately selecting separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we learn to separate by proposing a novel data-driven strategy to restrict the selection space and a learning-guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up to 72% and 37% on synthetic and real-world MILP benchmarks. Our work complements recent work on learning to select cutting planes and highlights the importance of separator management.
• Abstract（参考訳）: カット平面は、最適解のバウンダリ改善を促進するため、混合整数線形プログラム(MILP)の解決に不可欠である。 現代のMILPソルバは、様々な分離器を頼りに、解法プロセス中に分離器を頻繁に呼び出すことによって、様々な切断面を生成する。 本研究は, セパレータを適切に選択することでMILPソルバを劇的に高速化できることを示す。 組合せセパレータ選択空間は機械学習の課題を課すため、選択空間を制限するための新しいデータ駆動戦略と、制限空間上で学習誘導アルゴリズムを提案することで、分離することを学ぶ。 本手法は, 実世界のMILPベンチマークにおいて, 相対解時間を72%, 37%に向上させることにより, オープンソースのMILPソルバSCIPを効果的に高速化し, 動的に適用可能なインスタンス認識セパレータ構成を予測する。 我々の研究は、切削面の選択に関する最近の研究を補完し、セパレータ管理の重要性を強調している。

関連論文リスト

• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  SPARSEK Attention(SPARSEK Attention)は、計算およびメモリ障害を克服するために設計された、新しいスパースアテンション機構である。 提案手法では,各クエリに対して一定数のKVペアを選択するために,スコアリングネットワークと差別化可能なトップkマスク演算子であるSPARSEKを統合する。 実験結果から,SPARSEK注意は従来のスパースアテンション法よりも優れていた。
  論文  参考訳（メタデータ） (2024-06-24T15:55:59Z)
• Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming [61.59888010725235]
  混合整数線形プログラム(MILP)の解法における切削平面(カット)の役割 カット選択ポリシーを学習するための新しい階層型シーケンス/セットモデル(HEM)を提案する。 HEMは、(P1)-(P3)を同時に扱う最初のデータ駆動手法である。
  論文  参考訳（メタデータ） (2024-04-19T05:40:25Z)
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model [81.56473654324328]
  本稿では,強化学習によるカット選択ポリシーを学習するための新しい階層型シーケンスモデル(HEM)を提案する。 HEMはデータ駆動の観点から(P1)-(P3)のカット選択に対処できる最初の方法である。 実験の結果,HEMは人間設計および学習ベースラインと比較してMILPの解法効率を著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-02-01T04:59:55Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。 このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
  論文  参考訳（メタデータ） (2022-03-04T17:06:00Z)
• A Transferable Approach for Partitioning Machine Learning Models on Multi-Chip-Modules [8.224904698490626]
  マルチチップモジュール(MCM)は、機械学習アクセラレータの設計と製造コストを削減する。 本稿では, 深い強化学習フレームワークを用いて, 潜在的に無効な候補分割を出力し, 制約解法によって補正する戦略を提案する。 実ハードウェア上でのプロダクションスケールモデルBERTの評価により,RLポリシを用いて生成したパーティショニングのスループットが6.11%,5.85%向上したことが明らかとなった。
  論文  参考訳（メタデータ） (2021-12-07T23:40:28Z)
• Mixing Deep Learning and Multiple Criteria Optimization: An Application to Distributed Learning with Multiple Datasets [0.0]
  トレーニングフェーズは、マシンラーニングプロセスにおいて最も重要なステージです。 本研究では,特定の入力とラベルに関連付けられた出力との距離を基準として,複数の基準最適化モデルを構築した。 MNISTデータを用いた数値分類において,このモデルと数値実験を実現するためのスカラー化手法を提案する。
  論文  参考訳（メタデータ） (2021-12-02T16:00:44Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)
• Auxiliary-task Based Deep Reinforcement Learning for Participant Selection Problem in Mobile Crowdsourcing [30.124365580284888]
  モバイルのクラウドソーシングでは、複数の目標を達成するために、求職者からの位置情報対応タスクを参加者に選択する。 異なる MCS システムには異なる目標があり、ある MCS システムでも相反する目標が存在する可能性がある。 複数の目標を達成するために,様々なMCSシステムに適用可能な参加者選択アルゴリズムを設計することが重要である。
  論文  参考訳（メタデータ） (2020-08-25T15:02:54Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。 提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。 本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
  論文  参考訳（メタデータ） (2020-02-20T11:11:32Z)

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

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