論文の概要: Solving Mixed Integer Programs Using Neural Networks

• arxiv url: http://arxiv.org/abs/2012.13349v1
• Date: Wed, 23 Dec 2020 09:33:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-25 18:13:04.079653
• Title: Solving Mixed Integer Programs Using Neural Networks
• Title（参考訳）: ニューラルネットワークを用いた混合整数プログラムの解法
• Authors: Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols
• Abstract要約: 本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
• 参考スコア（独自算出の注目度）: 57.683491412480635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among instances in the data. This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. Neural Diving learns a deep neural network to generate multiple partial assignments for its integer variables, and the resulting smaller MIPs for un-assigned variables are solved with SCIP to construct high quality joint assignments. Neural Branching learns a deep neural network to make variable selection decisions in branch-and-bound to bound the objective value gap with a small tree. This is done by imitating a new variant of Full Strong Branching we propose that scales to large instances using GPUs. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each. Most instances in all the datasets combined have $10^3-10^6$ variables and constraints after presolve, which is significantly larger than previous learning approaches. Comparing solvers with respect to primal-dual gap averaged over a held-out set of instances, the learning-augmented SCIP is 2x to 10x better on all datasets except one on which it is $10^5$x better, at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.
• Abstract（参考訳）: 混合整数プログラミング(mip)ソルバは、何十年もの研究で開発された洗練されたヒューリスティックの配列に依存し、実際に遭遇する大規模mipインスタンスを解決する。 機械学習は、データ内のインスタンス間の共有構造を利用して、データからより優れたヒューリスティックを自動構築する。 本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 Neural Divingは、整数変数に対する複数の部分代入を生成するディープニューラルネットワークを学習し、その結果、未割り当て変数に対するより小さなMIPをSCIPで解決し、高品質な関節代入を構築する。 ニューラルブランチはディープニューラルネットワークを学び、分岐とバウンドの変数選択決定を行い、目的値ギャップを小さな木とバウンドする。 これは、GPUを使用して大規模インスタンスにスケールする、Full Strong Branchingの新しい変種を模倣することで実現される。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。 すべてのデータセットのほとんどのインスタンスは、10^3-10^6$変数を持ち、事前解決後の制約がある。 保持されたインスタンスセットの平均的なプリマル・デュアルギャップに対するソルバを比較すると、学習によるscipは10^5$x以上のデータセットを除いて、すべてのデータセットで2倍から10倍に向上する。 私たちの知る限りでは、大規模な実世界のアプリケーションデータセットとMIPLIBの両方において、SCIPよりも大きな改善を示す最初の学習アプローチです。

関連論文リスト

• MPruner: Optimizing Neural Network Size with CKA-Based Mutual Information Pruning [7.262751938473306]
  プルーニング(Pruning)は、ニューラルネットワークのサイズを減らし、数学的に精度の保存を保証している、よく確立されたテクニックである。 我々は,ベクトル類似性により相互情報を活用する新しいプルーニングアルゴリズムMPrunerを開発した。 MPrunerはCNNとトランスフォーマーベースのモデルで最大50%のパラメータとメモリ使用量の削減を実現した。
  論文  参考訳（メタデータ） (2024-08-24T05:54:47Z)
• Neural Attentive Circuits [93.95502541529115]
  我々は、NAC(Neural Attentive Circuits)と呼ばれる汎用的でモジュラーなニューラルアーキテクチャを導入する。 NACは、ドメイン知識を使わずに、ニューラルネットワークモジュールのパラメータ化と疎結合を学習する。 NACは推論時に8倍のスピードアップを達成するが、性能は3%以下である。
  論文  参考訳（メタデータ） (2022-10-14T18:00:07Z)
• End-to-End Learning of Deep Kernel Acquisition Functions for Bayesian Optimization [39.56814839510978]
  ニューラルネットワークに基づくカーネルを用いたベイズ最適化のためのメタラーニング手法を提案する。 我々のモデルは、複数のタスクから強化学習フレームワークによって訓練されている。 3つのテキスト文書データセットを用いた実験において,提案手法が既存の手法よりも優れたBO性能を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-01T00:42:31Z)
• Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networks [0.07614628596146598]
  二元活性化関数と連続または整数重み付きディープニューラルネットワーク(BDNN)について検討する。 BDNNは、古典的な混合整数計画解法により、大域的最適性に解けるような、有界な重み付き混合整数線形プログラムとして再構成可能であることを示す。 トレーニング中にBDNNの堅牢性を強制するロバストモデルが初めて提示される。
  論文  参考訳（メタデータ） (2021-10-21T18:02:58Z)
• Fully Dynamic Inference with Deep Neural Networks [19.833242253397206]
  Layer-Net(L-Net)とChannel-Net(C-Net)と呼ばれる2つのコンパクトネットワークは、どのレイヤやフィルタ/チャネルが冗長であるかをインスタンス毎に予測する。 CIFAR-10データセットでは、LC-Netは11.9$times$ less floating-point Operations (FLOPs) となり、他の動的推論手法と比較して最大3.3%精度が向上する。 ImageNetデータセットでは、LC-Netは最大1.4$times$ FLOPsを減らし、Top-1の精度は他の方法よりも4.6%高い。
  論文  参考訳（メタデータ） (2020-07-29T23:17:48Z)
• DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
  本稿では,ディープ・ニューラル・アーキテクチャーを効果的かつ効率的に探索するためのディバイド・アンド・コンカ(DC)手法を提案する。 ImageNetデータセットで75.1%の精度を達成しており、これは同じ検索空間を使った最先端の手法よりも高い。
  論文  参考訳（メタデータ） (2020-05-29T09:02:16Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming [11.712073757744452]
  深層ニューラルネットワークアーキテクチャにおいて,各ニューロンに重要なスコアを割り当てるための混合整数プログラム(MIP)を導入する。 我々は、トレーニングされたニューラルネットワークの全体的な精度を維持するために必要な臨界ニューロンの数(すなわち、高いスコアを持つ)を最小限に抑えるために、ソルバを駆動する。
  論文  参考訳（メタデータ） (2020-02-17T21:32:47Z)
• Large-Scale Gradient-Free Deep Learning with Recursive Local Representation Alignment [84.57874289554839]
  大規模データセット上でディープニューラルネットワークをトレーニングするには、重要なハードウェアリソースが必要である。 これらのネットワークをトレーニングするためのワークホースであるバックプロパゲーションは、本質的に並列化が難しいシーケンシャルなプロセスである。 本稿では、深層ネットワークのトレーニングに使用できるバックプロップに代わる、神経生物学的に有望な代替手段を提案する。
  論文  参考訳（メタデータ） (2020-02-10T16:20:02Z)
• Model Fusion via Optimal Transport [64.13185244219353]
  ニューラルネットワークのための階層モデル融合アルゴリズムを提案する。 これは、不均一な非i.d.データに基づいてトレーニングされたニューラルネットワーク間での"ワンショット"な知識伝達に成功していることを示す。
  論文  参考訳（メタデータ） (2019-10-12T22:07:15Z)

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

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