論文の概要: Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

• arxiv url: http://arxiv.org/abs/2302.01578v1
• Date: Fri, 3 Feb 2023 07:15:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-06 17:04:31.894871
• Title: Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning
• Title（参考訳）: コントラスト学習による整数線形プログラムの大規模領域探索
• Authors: Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, Benoit Steiner
• Abstract要約: 線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
• 参考スコア（独自算出の注目度）: 39.40838358438744
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance.
• Abstract（参考訳）: Integer Linear Programs (ILP) は、多数の組合せ最適化問題のモデリングと解決のための強力なツールである。 近年,Large Neborhood Search (LNS) はヒューリスティックアルゴリズムとして,ブランチやバウンドよりも高速にILPの高品質な解を見つけることができることが示されている。 しかし、LNSの性能を最大化する適切なヒューリスティックを見つける方法は未解決の問題である。 本稿では, 予備差, 一次積分, 生存率, 最高性能率などの指標によって測定された複数のICPベンチマークに対して, 最先端のリアルタイム性能を提供する新しい手法CL-LNSを提案する。 具体的には、CL-LNSは、計算が遅い専門家ヒューリスティックから正と負の解サンプルを収集し、対照的な損失を持つ新しい解を学習する。 グラフアテンションネットワークとよりリッチな機能セットを使用して、パフォーマンスをさらに向上しています。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  オフライン優先最適化は、LLM(Large Language Model)出力の品質を向上・制御するための重要な手法である。 我々は、人間の介入なしに、新しい最先端の選好最適化アルゴリズムを自動で発見する客観的発見を行う。 実験は、ロジスティックと指数的損失を適応的にブレンドする新しいアルゴリズムであるDiscoPOPの最先端性能を示す。
  論文  参考訳（メタデータ） (2024-06-12T16:58:41Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
  LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。 本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。 提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
  論文  参考訳（メタデータ） (2022-12-15T22:53:09Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。 我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
  論文  参考訳（メタデータ） (2022-11-26T00:01:01Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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