論文の概要: Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem

• arxiv url: http://arxiv.org/abs/2412.14382v1
• Date: Wed, 18 Dec 2024 22:32:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:32:32.750605
• Title: Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem
• Title（参考訳）: Balans:Mixed-Integerプログラミング問題に対するマルチArmed BanditsベースのAdaptive Large Neighborhood Search
• Authors: Junyang Cai, Serdar Kadioglu, Bistra Dilkina,
• Abstract要約: MIP(Mixed-Integer Programming)は、様々な重要な最適化問題のモデリングと解決のための強力なパラダイムである。 オンライン学習機能を備えたMIPのための適応型メタソリューションであるBaransを提案する。 Balansは、デフォルトのMIP解決器よりもパフォーマンスが大幅に向上し、どの最良地区にもコミットするより優れ、最先端のMIPの大規模検索よりも改善されている。
• 参考スコア（独自算出の注目度）: 13.381261742433367
• License:
• Abstract: Mixed-Integer Programming (MIP) is a powerful paradigm for modeling and solving various important combinatorial optimization problems. Recently, learning-based approaches have shown potential to speed up MIP solving via offline training that then guides important design decisions during search. However, a significant drawback of these methods is their heavy reliance on offline training, which requires collecting training datasets and computationally costly training epochs yet offering only limited generalization to unseen (larger) instances. In this paper, we propose Balans, an adaptive meta-solver for MIPs with online learning capability that does not require any supervision or apriori training. At its core, Balans is based on adaptive large-neighborhood search, operating on top of a MIP solver by successive applications of destroy and repair neighborhood operators. During the search, the selection among different neighborhood definitions is guided on the fly for the instance at hand via multi-armed bandit algorithms. Our extensive experiments on hard optimization instances show that Balans offers significant performance gains over the default MIP solver, is better than committing to any single best neighborhood, and improves over the state-of-the-art large-neighborhood search for MIPs. Finally, we release Balans as a highly configurable, MIP solver agnostic, open-source software.
• Abstract（参考訳）: MIP(Mixed-Integer Programming)は、様々な重要な組合せ最適化問題のモデル化と解決のための強力なパラダイムである。 近年、学習に基づくアプローチは、オフライントレーニングを通じてMIP解決を高速化する可能性を示し、検索時に重要な設計決定を導く。 しかし、これらの手法の重大な欠点は、オフライントレーニングに大きく依存していることであり、トレーニングデータセットの収集と計算コストのかかるエポシックなトレーニングを必要とするが、見当たらない(より大きな)インスタンスへの限定的な一般化しか提供していない。 本稿では,オンライン学習機能を備えたMIPのための適応型メタソリューションであるBaransを提案する。 Balansのコアとなるのは、MIPソルバ上で動作し、近隣のオペレータの破壊と修復の連続的な応用によって、適応的な大都市探索に基づいている。 検索中、複数の近傍定義の選択は、マルチアームのバンディットアルゴリズムを介して、手元にあるインスタンスに対して誘導される。 厳密な最適化インスタンスに関する広範な実験により、BaransはデフォルトのMIP解決器よりも大きなパフォーマンス向上を提供し、どの最良地区にもコミットするよりも優れており、最先端のMIPの大規模検索よりも改善されていることが示された。 最後に、Balansを高度に構成可能な、MIPソルバ非依存のオープンソースソフトウェアとしてリリースします。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• Moco: A Learnable Meta Optimizer for Combinatorial Optimization [5.359176539960004]
  Mocoは、現在の検索状態から抽出された特徴に基づいて、ソリューション構築手順を更新するグラフニューラルネットワークを学習する。 このメタトレーニング手順は、検索予算などの情報を得た探索手順中に見つかった全体的なベストソリューションをターゲットにしている。 Mocoは完全に学習可能なメタで、特定のローカル検索や分解の問題を一切利用しない。
  論文  参考訳（メタデータ） (2024-02-07T14:41:17Z)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  MAPFはLarge Neborhood Search(LNS)に基づいている 探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。 大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
  論文  参考訳（メタデータ） (2023-12-28T01:24:42Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。 提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。 その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
  論文  参考訳（メタデータ） (2022-11-01T21:33:46Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
  論文  参考訳（メタデータ） (2022-07-26T15:34:10Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  本稿では、混合整数(MIP)問題を解くための機械学習の動向について調査する。 本稿では、まず、MIPの定式化とプリミナリーと、MIPを解くための従来のアルゴリズムについて紹介する。 そして、機械学習とMIPアルゴリズムの異なる統合をさらに促進することを提唱する。
  論文  参考訳（メタデータ） (2022-03-06T05:03:37Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  フェデレートラーニング(FL)では、モデルトレーニングはクライアントに分散し、ローカルモデルは中央サーバによって集約される。 本稿では,各クライアントの差分プライバシ(DP)要件だけでなく,全体としてのトレーニング性能に制約された無線チャネル上でのFLトレーニング遅延を最小限に抑えることを目的とする。
  論文  参考訳（メタデータ） (2021-06-20T13:51:18Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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