論文の概要: Learning To Dive In Branch And Bound

• arxiv url: http://arxiv.org/abs/2301.09943v1
• Date: Tue, 24 Jan 2023 12:01:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-25 13:42:50.270452
• Title: Learning To Dive In Branch And Bound
• Title（参考訳）: 分岐と境界に潜ることを学ぶ
• Authors: Max B. Paulus, Andreas Krause
• Abstract要約: グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
• 参考スコア（独自算出の注目度）: 95.13209326119153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Primal heuristics are important for solving mixed integer linear programs, because they find feasible solutions that facilitate branch and bound search. A prominent group of primal heuristics are diving heuristics. They iteratively modify and resolve linear programs to conduct a depth-first search from any node in the search tree. Existing divers rely on generic decision rules that fail to exploit structural commonality between similar problem instances that often arise in practice. Therefore, we propose L2Dive to learn specific diving heuristics with graph neural networks: We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions based on the model's predictions. L2Dive is fully integrated into the open-source solver SCIP. We find that L2Dive outperforms standard divers to find better feasible solutions on a range of combinatorial optimization problems. For real-world applications from server load balancing and neural network verification, L2Dive improves the primal-dual integral by up to 7% (35%) on average over a tuned (default) solver baseline and reduces average solving time by 20% (29%).
• Abstract（参考訳）: 主ヒューリスティックは分岐探索と境界探索を容易にする実現可能な解を見つけるため、混合整数線形プログラムを解くのに重要である。 主なヒューリスティックのグループはダイビングヒューリスティックである。 線形プログラムを反復的に修正し、探索ツリー内の任意のノードから深度優先探索を行う。 既存のダイバーは、しばしば実際に発生する同様の問題インスタンス間の構造的共通性を利用しない一般的な決定ルールに依存している。 そこで我々はL2Diveを提案し、グラフニューラルネットワークを用いて特定の潜水ヒューリスティックを学習する:我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して、モデルの予測に基づいて潜水決定を行う。 L2DiveはオープンソースのソルバSCIPに完全に統合されている。 L2Diveは、様々な組合せ最適化問題において、より良い実現可能な解を求めるために、標準ダイバーよりも優れている。 サーバロードバランシングとニューラルネットワーク検証による実世界のアプリケーションでは、l2diveは、チューニングされた(デフォルト)ソルバベースラインよりも平均で最大7%(35%)改善され、平均解決時間が20%(29%)削減される。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。 我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
  論文  参考訳（メタデータ） (2022-11-26T00:01:01Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  0-1整数線形プログラムの緩和を解くために,高速でスケーラブルなデータ駆動型手法を提案する。 グラフニューラルネットワーク(GNN)とラグランジュ分解に基づくアルゴリズムであるFastDOGを用いる。
  論文  参考訳（メタデータ） (2022-05-23T21:09:41Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。 また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。 木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-01-25T17:37:34Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。 モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。 数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
  論文  参考訳（メタデータ） (2021-08-15T21:32:47Z)
• A generalized quadratic loss for SVM and Deep Neural Networks [0.0]
  我々は、いくつかの監督されたバイナリ分類タスクと回帰タスクを検討するが、SVMとDeep Learningは現在、最高の一般化パフォーマンスを示す。 パターン相関を検討する学習問題に対する一般化二次損失に関する研究[3]を拡張し、パターンがより高密度に分布する入力空間領域に学習問題を集中させる。
  論文  参考訳（メタデータ） (2021-02-15T15:49:08Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2020-12-23T09:33:11Z)

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

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