論文の概要: Neur2BiLO: Neural Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2402.02552v1
- Date: Sun, 4 Feb 2024 15:54:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 19:02:16.281054
- Title: Neur2BiLO: Neural Bilevel Optimization
- Title(参考訳): Neur2BiLO:ニューラルバイレベル最適化
- Authors: Justin Dumouchelle, Esther Julien, Jannis Kurtz, Elias B. Khalil
- Abstract要約: Neur2BiLOは、リーダーまたはフォロワーの値関数のニューラルネットワーク近似を、簡単に解ける混合整数プログラムに組み込む。
両レベルのクナプサック断面積問題、ネットワークセキュリティの「クリティカルノードゲーム」、提供者による医療問題、交通計画からの個別ネットワーク設計に対して、高品質なソリューションを極端に高速に生成する。
- 参考スコア(独自算出の注目度): 17.34387773676538
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bilevel optimization deals with nested problems in which a leader takes the
first decision to minimize their objective function while accounting for a
follower's best-response reaction. Constrained bilevel problems with integer
variables are particularly notorious for their hardness. While exact solvers
have been proposed for mixed-integer linear bilevel optimization, they tend to
scale poorly with problem size and are hard to generalize to the non-linear
case. On the other hand, problem-specific algorithms (exact and heuristic) are
limited in scope. Under a data-driven setting in which similar instances of a
bilevel problem are solved routinely, our proposed framework, Neur2BiLO, embeds
a neural network approximation of the leader's or follower's value function,
trained via supervised regression, into an easy-to-solve mixed-integer program.
Neur2BiLO serves as a heuristic that produces high-quality solutions extremely
fast for the bilevel knapsack interdiction problem, the "critical node game"
from network security, a donor-recipient healthcare problem, and discrete
network design from transportation planning. These problems are diverse in that
they have linear or non-linear objectives/constraints and integer or
mixed-integer variables, making Neur2BiLO unique in its versatility.
- Abstract(参考訳): 二段階最適化は、リーダーが最初の決定を下して客観的な機能を最小化し、従者の最善の反応を考慮し、ネストした問題を扱う。
整数変数の制約付き双レベル問題は、その困難さで特に悪名高い。
混合整数線形双レベル最適化には正確な解法が提案されているが、問題の大きさに乏しく、非線形の場合への一般化が困難である。
一方、問題固有のアルゴリズム(実演とヒューリスティック)は範囲が限られている。
両レベル問題の類似したインスタンスを日常的に解決するデータ駆動設定の下で、提案するフレームワークNeur2BiLOは、教師付き回帰によってトレーニングされたリーダまたはフォロワーの値関数のニューラルネットワーク近似を、容易に解ける混合整数プログラムに組み込む。
Neur2BiLOは、双方向のknapsack断面積問題、ネットワークセキュリティからの"クリティカルノードゲーム"、ドナーの医療問題、交通計画からの離散ネットワーク設計に対して、非常に高速な高品質なソリューションを生成するヒューリスティックとして機能する。
これらの問題は、線形あるいは非線形の目的/制約と整数または混合整数変数を持つという点で多様であり、Neur2BiLOはその汎用性においてユニークである。
関連論文リスト
- Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-02-13T21:28:53Z) - Global and Preference-based Optimization with Mixed Variables using
Piecewise Affine Surrogates [1.30536490219656]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
本稿では,2種類の探索関数を導入し,混合整数線形計画解法を用いて実現可能な領域を効率的に探索する。
提案アルゴリズムは,既存の手法よりもよく,あるいは同等の結果が得られることが多い。
論文 参考訳(メタデータ) (2023-02-09T15:04:35Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳(メタデータ) (2023-01-24T12:01:45Z) - From Kernel Methods to Neural Networks: A Unifying Variational
Formulation [25.6264886382888]
演算子と一般ラドン領域ノルムに依存する統一正規化関数を提案する。
我々のフレームワークは、多種多様な正規化演算子、または同等に、幅広い浅層ニューラルネットワークに対して、普遍的な近似を保証する。
論文 参考訳(メタデータ) (2022-06-29T13:13:53Z) - Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
フェデレーテッド・ラーニング(FL)は、分散した位置データの上で、将来性のあるプライバシ保護機械学習パラダイムである。
FLにおける雑音ラベルの効果を緩和する学習に基づく再重み付け手法を提案する。
提案手法は,複数の実世界のデータセットにおいて,各種ベースラインと比較して優れた性能を示した。
論文 参考訳(メタデータ) (2022-06-11T16:21:17Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳(メタデータ) (2022-05-03T16:40:22Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳(メタデータ) (2022-03-01T18:20:01Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳(メタデータ) (2022-01-31T18:17:25Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳(メタデータ) (2021-07-26T16:18:43Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳(メタデータ) (2020-05-29T00:13:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。