論文の概要: Learning for Spatial Branching: An Algorithm Selection Approach
- arxiv url: http://arxiv.org/abs/2204.10834v1
- Date: Fri, 22 Apr 2022 17:23:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-25 14:45:25.015592
- Title: Learning for Spatial Branching: An Algorithm Selection Approach
- Title（参考訳）: 空間分岐のための学習:アルゴリズム選択アプローチ
- Authors: Bissan Ghaddar, Ignacio G\'omez-Casares, Julio Gonz\'alez-D\'iaz,
Brais Gonz\'alez-Rodr\'iguez, Beatriz Pateiro-L\'opez, Sof\'ia
Rodr\'iguez-Ballesteros
- Abstract要約: 本研究では,非線形最適化問題の文脈で分岐学習フレームワークを開発し,その有効性を示す。
提案した学習は、インスタンス固有の機能に基づいてオフラインで実行され、新しいインスタンスを解く際の計算オーバーヘッドがない。
異なるベンチマークインスタンスの実験では、学習ベースの分岐ルールが標準ルールを大幅に上回っていることが示されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The use of machine learning techniques to improve the performance of
branch-and-bound optimization algorithms is a very active area in the context
of mixed integer linear problems, but little has been done for non-linear
optimization. To bridge this gap, we develop a learning framework for spatial
branching and show its efficacy in the context of the
Reformulation-Linearization Technique for polynomial optimization problems. The
proposed learning is performed offline, based on instance-specific features and
with no computational overhead when solving new instances. Novel graph-based
features are introduced, which turn out to play an important role for the
learning. Experiments on different benchmark instances from the literature show
that the learning-based branching rule significantly outperforms the standard
rules.
- Abstract（参考訳）: 分岐とバウンドの最適化アルゴリズムの性能向上のための機械学習技術の利用は、混合整数線形問題において非常に活発な分野であるが、非線形最適化ではほとんど行われていない。
このギャップを埋めるため、我々は空間分岐学習フレームワークを開発し、多項式最適化問題に対する修正-線形化手法の文脈でその有効性を示す。
提案した学習は、インスタンス固有の機能に基づいてオフラインで実行され、新しいインスタンスを解く際の計算オーバーヘッドがない。
新しいグラフベースの機能が導入され、学習に重要な役割を果たすことが判明した。
文献の異なるベンチマークインスタンスを用いた実験では、学習に基づく分岐規則が標準規則を大きく上回っていることが示されている。
関連論文リスト
- Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
論文 参考訳（メタデータ） (2024-09-07T19:52:14Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Maximum Optimality Margin: A Unified Approach for Contextual Linear
Programming and Inverse Linear Programming [10.06803520598035]
我々は、下流最適化の最適条件によって機械学習損失関数が機能する最大最適マージンと呼ばれる問題に対する新しいアプローチを開発する。
論文 参考訳（メタデータ） (2023-01-26T17:53:38Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳（メタデータ） (2022-06-01T23:26:51Z) - Teaching Networks to Solve Optimization Problems [13.803078209630444]
反復解法をトレーニング可能なパラメトリック集合関数に置き換えることを提案する。
このようなパラメトリックな(集合)関数を学習することで、様々な古典的最適化問題を解くことができることを示す。
論文 参考訳（メタデータ） (2022-02-08T19:13:13Z) - OASIS: An Active Framework for Set Inversion [4.014524824655106]
本稿では,二項分類問題として定式化することで,集合反転問題の解法を提案する。
従来の学習手法に比べて少ないデータポイントで同じレベルの精度を達成できる、新しい強力なテクニックのファミリーであるアクティブラーニングに重点を置いている。
論文 参考訳（メタデータ） (2021-05-31T15:04:43Z) - Linear Matrix Factorization Embeddings for Single-objective Optimization
Landscapes [0.755972004983746]
ブラックボックス最適化では、機能は$(x,f(x))$サンプルのセットから導出する必要がある。
行列因数分解による線形次元の減少は、異なる問題インスタンス間の相関関係のより良い検出に大きく寄与することを示す。
論文 参考訳（メタデータ） (2020-09-30T08:46:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。