論文の概要: Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation

• arxiv url: http://arxiv.org/abs/2310.14161v1
• Date: Sun, 22 Oct 2023 03:15:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-25 01:33:01.312204
• Title: Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation
• Title（参考訳）: 逆インスタンス拡張による厳密解法の一般化の促進
• Authors: Haoyang Liu and Yufei Kuang and Jie Wang and Xijun Li and Yongdong Zhang and Feng Wu
• Abstract要約: Adarは、模倣学習ベース(ILベース)と強化学習ベース(RLベース)の両方の一般化を理解し、改善するためのフレームワークである。
• 参考スコア（独自算出の注目度）: 62.738582127114704
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Machine learning has been successfully applied to improve the efficiency of Mixed-Integer Linear Programming (MILP) solvers. However, the learning-based solvers often suffer from severe performance degradation on unseen MILP instances -- especially on large-scale instances from a perturbed environment -- due to the limited diversity of training distributions. To tackle this problem, we propose a novel approach, which is called Adversarial Instance Augmentation and does not require to know the problem type for new instance generation, to promote data diversity for learning-based branching modules in the branch-and-bound (B&B) Solvers (AdaSolver). We use the bipartite graph representations for MILP instances and obtain various perturbed instances to regularize the solver by augmenting the graph structures with a learned augmentation policy. The major technical contribution of AdaSolver is that we formulate the non-differentiable instance augmentation as a contextual bandit problem and adversarially train the learning-based solver and augmentation policy, enabling efficient gradient-based training of the augmentation policy. To the best of our knowledge, AdaSolver is the first general and effective framework for understanding and improving the generalization of both imitation-learning-based (IL-based) and reinforcement-learning-based (RL-based) B&B solvers. Extensive experiments demonstrate that by producing various augmented instances, AdaSolver leads to a remarkable efficiency improvement across various distributions.
• Abstract（参考訳）: 機械学習は、MILP(Mixed-Integer Linear Programming)ソルバの効率向上に成功している。 しかしながら、学習ベースのソルバは、トレーニング分布の多様性が限定されているため、目に見えないMILPインスタンス(特に摂動環境の大規模インスタンス)の厳しいパフォーマンス劣化に悩まされることが多い。 この問題に対処するため,AdaSolver(Adversarial Instance Augmentation)と呼ばれる新しい手法を提案し,新しいインスタンス生成における問題タイプを知る必要はなく,分岐(B&B)ソルバー(AdaSolver)における学習ベース分岐モジュールのデータ多様性を促進する。 両部グラフ表現をMILPインスタンスに使用し、様々な摂動インスタンスを取得し、グラフ構造を学習拡張ポリシーで拡張することにより、ソルバを正規化する。 AdaSolverの主な技術的貢献は、非微分不可能なインスタンス拡張を文脈的包帯問題として定式化し、学習に基づく解法と拡張ポリシーを逆向きに訓練し、拡張ポリシーの効率的な勾配に基づく訓練を可能にすることである。 我々の知る限り、AdaSolverは、模倣学習ベース(ILベース)と強化学習ベース(RLベース)の両方のB&Bソルバの一般化を理解し、改善するための、最初の汎用的で効果的なフレームワークである。 広範囲な実験により、様々な拡張インスタンスを生成することで、adasolverは様々なディストリビューションで顕著な効率改善をもたらすことが示されている。

関連論文リスト

• From Novice to Expert: LLM Agent Policy Optimization via Step-wise Reinforcement Learning [62.54484062185869]
  本稿では,エージェントの強化学習プロセスの最適化にステップワイド報酬を利用するStepAgentを紹介する。 エージェント反射とポリシー調整を容易にする暗黙の逆・逆の強化学習手法を提案する。
  論文  参考訳（メタデータ） (2024-11-06T10:35:11Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  拡散生成モデルはより広い範囲の解を考えることができ、学習パラメータによるより強力な一般化を示す。 拡散生成モデルの本質的な分布学習を利用して高品質な解を学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。 本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。 本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
  論文  参考訳（メタデータ） (2024-01-11T15:02:15Z)
• Attention, Filling in The Gaps for Generalization in Routing Problems [5.210197476419621]
  本稿では,既存のモデルの理解と改善を通じて,分野の統合を促進することを目的とする。 我々はまず,Sparse Dynamic Attention のための Kool et al. 法とその損失関数を適用することで,モデルの相違を第一に狙う。 次に、特定のシナリオにおける単一インスタンストレーニングよりも優れたパフォーマンスを示す混合インスタンストレーニングメソッドを使用することで、固有の違いをターゲットとします。
  論文  参考訳（メタデータ） (2022-07-14T21:36:51Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Dynamics Generalization via Information Bottleneck in Deep Reinforcement Learning [90.93035276307239]
  本稿では,RLエージェントのより優れた一般化を実現するために,情報理論正則化目標とアニーリングに基づく最適化手法を提案する。 迷路ナビゲーションからロボットタスクまで、さまざまな領域において、我々のアプローチの極端な一般化の利点を実証する。 この研究は、タスク解決のために冗長な情報を徐々に取り除き、RLの一般化を改善するための原則化された方法を提供する。
  論文  参考訳（メタデータ） (2020-08-03T02:24:20Z)

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

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