論文の概要: Improving the filtering of Branch-And-Bound MDD solver (extended)

• arxiv url: http://arxiv.org/abs/2104.11951v1
• Date: Sat, 24 Apr 2021 13:42:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-28 13:05:26.171250
• Title: Improving the filtering of Branch-And-Bound MDD solver (extended)
• Title（参考訳）: 分岐結合型MDDソルバのフィルタリング改善(拡張)
• Authors: Xavier Gillard, Vianney Copp\'e, Pierre Schaus, Andr\'e Augusto Cire
• Abstract要約: 本稿では,多値決定図(MDD)に基づく制約最適化解法の効率向上のための2つのプルーニング手法を提案し,評価する。 Bergmanらによって提案されたブランチ・アンド・バウンド・フレームワークを採用している。 2016年、動的プログラムを最適に解く。
• 参考スコア（独自算出の注目度）: 11.728147523456702
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.
• Abstract（参考訳）: 本稿では,マルチ値決定ダイアグラム(mdd)に基づく制約最適化ソルバの効率を高めるための2つのプルーニング手法を提案し,評価する。 Bergmanらによって提案されたブランチ・アンド・バウンド・フレームワークを採用している。 2016年、動的プログラムを最適に解く。 特に,本論文では,局所的バウンド (LocB) と粗大な上行プルーニング (RUB) の有効性について述べる。 LocBは、興味深いノードの探索を避けるために、近似MDD構造を利用する新しい効果的なルールである。 rubは、有界幅mddの開発中に探索空間を減らすための規則である。 最大独立セット問題(MISP)、最大カット問題(MCP)、最大2サスティフィビリティ問題(MAX2SAT)、旅行セールスマン問題(TSPTW)について行った実験は、粗アップパーバウンドおよび局所リバウンドプルーニングがMDDとの分岐とバウンドに基づく最適化問題に大きな影響を与えることを示す証拠である。 特に、rubは優れた結果をもたらすが、モデルを定義するのに多少の労力を要することを示している。 また、locbはユーザから提供された情報を必要とせずに、自動的に大幅な改善を提供する。 最後に,ラフアップパーバウンドとローカルバウンドプルーニングは相互排他的ではないことも示し,それらの組み合わせによる利益は,各手法の使用による個別の利益を上回っている。

関連論文リスト

• 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)
• 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)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Advancing Model Pruning via Bi-level Optimization [89.88761425199598]
  イテレーティブ・マグニチュード・プルーニング(IMP)は,「入賞券」の発見に成功するプルーニング法である ワンショットプルーニング法が開発されているが、これらのスキームは通常IMPほど勝利のチケットを見つけることができない。 提案手法は,双線形問題構造を持つBLO問題の特別なクラスであることを示す。
  論文  参考訳（メタデータ） (2022-10-08T19:19:29Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。 この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。 ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
  論文  参考訳（メタデータ） (2021-10-27T05:37:12Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Strong Optimal Classification Trees [8.10995244893652]
  最適二分分類木を学習するための直感的なフローベースMIO定式化を提案する。 我々の定式化は、解釈可能かつ公平な決定木の設計を可能にするために、サイド制約を満たすことができる。 提案手法は最先端MIO技術よりも29倍高速であることを示す。
  論文  参考訳（メタデータ） (2021-03-29T21:40:58Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)
• Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization [4.649999862713523]
  我々は、整数格子上の領域である連続利益(CPM-MS)問題を形成する。 格子に基づく二重グリードアルゴリズムを導入し, 定数近似を求める。 本稿では,格子型反復プルーニング手法を提案し,探索空間を効果的に縮小することができる。
  論文  参考訳（メタデータ） (2020-04-12T05:35:19Z)
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting [24.90164851620799]
  非等化因子マルコフ決定過程(FMDP)における強化学習の研究 FMDPに対する2つの近似およびオラクル効率アルゴリズムを提案する。 我々のオラクル効率のアルゴリズムは、コンピュータネットワーク管理シミュレーションにおいて、これまで提案されていた近似アルゴリズムよりも優れていた。
  論文  参考訳（メタデータ） (2020-02-06T15:19:53Z)

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

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