論文の概要: Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs

• arxiv url: http://arxiv.org/abs/2107.10201v1
• Date: Wed, 21 Jul 2021 16:43:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-22 14:02:21.704865
• Title: Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Title（参考訳）: 混合整数プログラムのための大規模近傍探索アルゴリズムの学習
• Authors: Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, Vinod Nair
• Abstract要約: 混合整数プログラム(MIP)に対する学習型LSSアプローチの検討 我々は、既存のMIPソルバとともに初期代入を生成する代入よりも確率分布を表現するために、ニューラルダイビングモデルを訓練する。 そこで我々はニューラル近隣選択ポリシーを訓練し,各ステップで探索地区を選択する。
• 参考スコア（独自算出の注目度）: 6.084888301899142
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Neighborhood Search (LNS) is a combinatorial optimization heuristic that starts with an assignment of values for the variables to be optimized, and iteratively improves it by searching a large neighborhood around the current assignment. In this paper we consider a learning-based LNS approach for mixed integer programs (MIPs). We train a Neural Diving model to represent a probability distribution over assignments, which, together with an existing MIP solver, generates an initial assignment. Formulating the subsequent search steps as a Markov Decision Process, we train a Neural Neighborhood Selection policy to select a search neighborhood at each step, which is searched using a MIP solver to find the next assignment. The policy network is trained using imitation learning. We propose a target policy for imitation that, given enough compute resources, is guaranteed to select the neighborhood containing the optimal next assignment across all possible choices for the neighborhood of a specified size. Our approach matches or outperforms all the baselines on five real-world MIP datasets with large-scale instances from diverse applications, including two production applications at Google. At large running times it achieves $2\times$ to $37.8\times$ better average primal gap than the best baseline on three of the datasets.
• Abstract（参考訳）: large neighborhood search (lns) は組合せ最適化ヒューリスティックであり、最適化される変数の値の割り当てから始まり、現在の割り当ての周りに大きな近傍を探索することで反復的に改善する。 本稿では、混合整数プログラム(MIP)に対する学習に基づくLSSアプローチを検討する。 我々は、既存のMIPソルバとともに初期割り当てを生成する代入よりも確率分布を表現するために、ニューラルダイビングモデルを訓練する。 その後の探索ステップをマルコフ決定プロセスとして定式化し、神経近傍選択ポリシーを訓練し、各ステップで探索近傍を選択し、mipソルバを用いて探索して次の課題を見つける。 政策ネットワークは模倣学習を用いて訓練される。 我々は,十分な計算資源が与えられた場合,任意の大きさの近傍に対して,最適な次の割り当てを含む近傍を選択することを保証した,模倣のためのターゲットポリシーを提案する。 当社のアプローチは,Googleの2つの実運用アプリケーションを含む,さまざまなアプリケーションからの大規模インスタンスを備えた,5つの実世界のMIPデータセットのベースラインをすべて一致あるいは上回るものです。 大規模な実行時には、データセットの3つの最良ベースラインよりも平均的プリミティブギャップが2ドルから37.8ドルに向上する。

関連論文リスト

• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [8.15681999722805]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs [5.28005598366543]
  ニューラルダイビング(ND)は、混合プログラム(MIP)における部分的な離散変数代入を生成する学習ベースのアプローチの1つである。 カバー範囲を最適化するためのポストホック法と学習に基づくアプローチを導入する。 実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。
  論文  参考訳（メタデータ） (2023-08-01T07:03:16Z)
• OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural Architecture Search [79.36688444492405]
  once-for-All(OFA)は、異なるリソース制約を持つデバイスのための効率的なアーキテクチャを探索する問題に対処するために設計された、ニューラルネットワーク検索(NAS)フレームワークである。 我々は,探索段階を多目的最適化問題として明示的に考えることにより,効率の追求を一歩進めることを目指している。
  論文  参考訳（メタデータ） (2023-03-23T21:30:29Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Multi-Task Learning for Sparsity Pattern Heterogeneity: Statistical and Computational Perspectives [10.514866749547558]
  マルチタスク学習(MTL)において、複数の線形モデルがデータセットの集合上で協調的に訓練される問題を考える。 我々のフレームワークの重要な特徴は、回帰係数のスパーシティパターンと非ゼロ係数の値がタスク間で異なることである。 提案手法は,1) 係数のサポートを個別に促進し,2) 非ゼロ係数の値を類似させることにより,タスク間の情報共有を奨励する。 これにより、非ゼロ係数値がタスク間で異なる場合でも、モデルが可変選択中に強度を借りることができる。
  論文  参考訳（メタデータ） (2022-12-16T19:52:25Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2020-12-23T09:33:11Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations [21.68175843347951]
  本稿では,ユーザとイテムのインタラクションデータを用いて,検索可能な構造を直接学習するために,Deep Retrieval(DR)を提案する。 DRは、産業レコメンデーションシステムのために数億のアイテムをスケールで展開した最初の非ANNアルゴリズムの1つである。
  論文  参考訳（メタデータ） (2020-07-12T06:23:51Z)
• MOPS-Net: A Matrix Optimization-driven Network forTask-Oriented 3D Point Cloud Downsampling [86.42733428762513]
  MOPS-Netは行列最適化のための新しい解釈可能な深層学習手法である。 我々はMOPS-Netが様々なタスクに対して最先端の深層学習手法に対して好適な性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-05-01T14:01:53Z)

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

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