論文の概要: DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization

• arxiv url: http://arxiv.org/abs/2301.12251v1
• Date: Sat, 28 Jan 2023 17:03:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-31 18:11:08.922317
• Title: DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization
• Title（参考訳）: DeciLS-PBO:擬似ブール最適化のための効率的な局所探索法
• Authors: Luyu Jiang, Dantong Ouyang, Qi Zhang, and Liming Zhang
• Abstract要約: PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
• 参考スコア（独自算出の注目度）: 10.513103815142731
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Local search is an effective method for solving large-scale combinatorial optimization problems, and it has made remarkable progress in recent years through several subtle mechanisms. In this paper, we found two ways to improve the local search algorithms in solving Pseudo-Boolean Optimization(PBO): Firstly, some of those mechanisms such as unit propagation are merely used in solving MaxSAT before, which can be generalized to solve PBO as well; Secondly, the existing local search algorithms utilize the heuristic on variables, so-called score, to mainly guide the search. We attempt to gain more insights into the clause, as it plays the role of a middleman who builds a bridge between variables and the given formula. Hence, we first extended the combination of unit propagation-based decimation algorithm to PBO problem, giving a further generalized definition of unit clause for PBO problem, and apply it to the existing solver LS-PBO for constructing an initial assignment; then, we introduced a new heuristic on clauses, dubbed care, to set a higher priority for the clauses that are less satisfied in current iterations. Experiments on three real-world application benchmarks including minimum-width confidence band, wireless sensor network optimization, and seating arrangement problems show that our algorithm DeciLS-PBO has a promising performance compared to the state-of-the-art algorithms.
• Abstract（参考訳）: 局所探索は大規模組合せ最適化問題を解く効果的な手法であり,近年,いくつかの微妙なメカニズムにより著しい進歩を遂げている。 本稿では,PBO(Pseudo-Boolean Optimization)の解法において,局所探索アルゴリズムを改善する2つの方法を見出した。まず,PBOの解法として一般化可能なMaxSATの解法において,単位伝搬などの機構を単に用いているだけであり,既存の局所探索アルゴリズムでは変数のヒューリスティック(英語版)(いわゆるスコア)を用いて探索を指導している。 我々は、変数と与えられた式の間のブリッジを構築する中間者の役割を担っているので、この条項に関するさらなる洞察を得ようと試みる。 そこで我々はまず,PBO問題への単位伝搬に基づくデシミテーションアルゴリズムの組合せを拡張し,PBO問題に対する単位節の定義をさらに一般化し,初期割り当てを構築するための既存の解法LS-PBOに適用した。 最小帯域信頼バンド,無線センサネットワーク最適化,座席配置問題を含む3つの実世界のアプリケーションベンチマーク実験により,我々のアルゴリズムであるDeciLS-PBOが最先端のアルゴリズムと比較して有望な性能を示した。

関連論文リスト

• 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)
• ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization [14.371138535749036]
  PBOの代表的なローカルサーチソルバはLSPBOである。 動的スコアリング機構によりLSPBOを改良し、ハード制約のスコアと目標関数のスコアのバランスを動的に調整する。 この改良されたLSPBOの上に,最初の並列局所探索PBOソルバを開発した。
  論文  参考訳（メタデータ） (2024-07-31T16:30:04Z)
• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
  論文  参考訳（メタデータ） (2022-04-27T08:40:33Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• 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)

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

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