論文の概要: LEO: Learning Efficient Orderings for Multiobjective Binary Decision
Diagrams
- arxiv url: http://arxiv.org/abs/2307.03171v1
- Date: Thu, 6 Jul 2023 17:52:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-07 12:55:43.489873
- Title: LEO: Learning Efficient Orderings for Multiobjective Binary Decision
Diagrams
- Title（参考訳）: LEO:多目的2値決定図のための効率的な順序付け学習
- Authors: Rahul Patel, Elias B. Khalil
- Abstract要約: 変数の順序付けは、緩和あるいは制限されたBDDから派生した境界の大きさや品質に大きな影響を与える可能性があることを示す。
列挙時間を削減する効率的な変数順序付けを見つけるための教師付き学習手法を提案する。
実験により、LEOは一般的な順序付け戦略やアルゴリズム構成よりも30～300%、PF列挙では10～200%高速であることが示されている。
- 参考スコア（独自算出の注目度）: 4.702456193042534
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Approaches based on Binary decision diagrams (BDDs) have recently achieved
state-of-the-art results for multiobjective integer programming problems. The
variable ordering used in constructing BDDs can have a significant impact on
their size and on the quality of bounds derived from relaxed or restricted BDDs
for single-objective optimization problems. We first showcase a similar impact
of variable ordering on the Pareto frontier (PF) enumeration time for the
multiobjective knapsack problem, suggesting the need for deriving variable
ordering methods that improve the scalability of the multiobjective BDD
approach. To that end, we derive a novel parameter configuration space based on
variable scoring functions which are linear in a small set of interpretable and
easy-to-compute variable features. We show how the configuration space can be
efficiently explored using black-box optimization, circumventing the curse of
dimensionality (in the number of variables and objectives), and finding good
orderings that reduce the PF enumeration time. However, black-box optimization
approaches incur a computational overhead that outweighs the reduction in time
due to good variable ordering. To alleviate this issue, we propose LEO, a
supervised learning approach for finding efficient variable orderings that
reduce the enumeration time. Experiments on benchmark sets from the knapsack
problem with 3-7 objectives and up to 80 variables show that LEO is ~30-300%
and ~10-200% faster at PF enumeration than common ordering strategies and
algorithm configuration. Our code and instances are available at
https://github.com/khalil-research/leo.
- Abstract（参考訳）: 双対決定図(BDD)に基づくアプローチは、最近、多目的整数プログラミング問題に対する最先端の結果を得た。
BDDの構築に使用される変数の順序付けは、そのサイズや、単一目的の最適化問題に対する緩和あるいは制限されたBDDから派生したバウンダリの品質に大きな影響を与える可能性がある。
我々はまず,多目的ナップサック問題に対するpareto frontier(pf)列挙時間に対する変数順序付けの類似性を示し,多目的bddアプローチのスケーラビリティを向上させる変数順序付けメソッドの導出の必要性を示唆する。
そこで我々は,小さな解釈可能かつ容易に計算可能な変数特徴セットにおいて線形な変数スコアリング関数に基づいて,新しいパラメータ構成空間を導出する。
ブラックボックス最適化を用いて構成空間を効率的に探索し、次元の呪いを回避し(変数数と目的数)、PF列挙時間を短縮する優れた順序付けを見つける方法を示す。
しかし、ブラックボックス最適化アプローチは、良好な変数順序付けによる時間の削減よりも大きい計算オーバーヘッドを伴います。
この問題を軽減するために、列挙時間を削減する効率的な変数順序付けを見つけるための教師付き学習手法LEOを提案する。
クナプサック問題の3～7の目的と最大80の変数によるベンチマークセットの実験では、LEOは一般的な順序付け戦略やアルゴリズム構成よりも30～300%、PF列挙では10～200%高速であることが示されている。
私たちのコードとインスタンスはhttps://github.com/khalil-research/leoで利用可能です。
関連論文リスト
- Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。
目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。
そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
論文 参考訳（メタデータ） (2025-02-13T01:27:11Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning
to Sparsify [19.821484909092913]
まず、問題に対するすべての実行可能なソリューションを表すグラフを構築するバイナリ意思決定図(BDD)に注目します。
機械学習(ML)を用いて、制限されたBDDが多目的最適化にどのように適応できるかを検討する。
MorBDDは、非常に小さな制限されたBDDを、優れた近似品質で、幅制限の制限されたBDDよりも優れ、よく知られた進化的アルゴリズムNSGA-IIを作るのに非常に効果的です。
論文 参考訳（メタデータ） (2024-03-04T21:04:54Z) - A Computationally Efficient Sparsified Online Newton Method [48.78646010774149]
Sparsified Online Newton (SONew) はメモリ効率の良い2次アルゴリズムである。
最大で30%の高速化,3.4%の妥当性向上,80%のトレーニング損失の相対的改善を実現しています。
論文 参考訳（メタデータ） (2023-11-16T18:44:22Z) - Large-Batch, Iteration-Efficient Neural Bayesian Design Optimization [37.339567743948955]
本稿では,BOの限界に対処するための新しいベイズ最適化フレームワークを提案する。
我々の重要な貢献は、高度にスケーラブルでサンプルベースの取得機能であり、非支配的な目的のソートを実行する。
我々は,ベイズ型ニューラルネットワークサロゲートと組み合わせることで,最小限の反復数でデータ集約環境に有効であることを示す。
論文 参考訳（メタデータ） (2023-06-01T19:10:57Z) - 3D Video Object Detection with Learnable Object-Centric Global
Optimization [65.68977894460222]
対応性に基づく最適化は3次元シーン再構成の基盤となるが、3次元ビデオオブジェクト検出では研究されていない。
オブジェクト中心の時間対応学習と特徴量付きオブジェクトバンドル調整を備えた、エンドツーエンドで最適化可能なオブジェクト検出器であるBA-Detを提案する。
論文 参考訳（メタデータ） (2023-03-27T17:39:39Z) - Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
提案手法は, 目的関数の断片的なアフィンサロゲートを, 実現可能なサンプル上に構築することに基づいている。
この2つのアルゴリズムは、制約なしおよび制約付き混合変数ベンチマーク問題に対して評価される。
論文 参考訳（メタデータ） (2023-02-09T15:04:35Z) - MBORE: Multi-objective Bayesian Optimisation by Density-Ratio Estimation [0.01652719262940403]
最適化問題は、しばしば計算的に、あるいは金銭的にコストがかかる複数の矛盾する目標を持つ。
単代理ベイズ最適化(BO)は、そのようなブラックボックス関数を最適化するための一般的なモデルベースのアプローチである。
BOREによるBOの先行研究を多目的設定に拡張する。
論文 参考訳（メタデータ） (2022-03-31T09:27:59Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Learning the Step-size Policy for the Limited-Memory
Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。
入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。
ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
論文 参考訳（メタデータ） (2020-10-03T09:34:03Z) - MOPS-Net: A Matrix Optimization-driven Network forTask-Oriented 3D Point
Cloud Downsampling [86.42733428762513]
MOPS-Netは行列最適化のための新しい解釈可能な深層学習手法である。
我々はMOPS-Netが様々なタスクに対して最先端の深層学習手法に対して好適な性能が得られることを示す。
論文 参考訳（メタデータ） (2020-05-01T14:01:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。