論文の概要: ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization
- arxiv url: http://arxiv.org/abs/2407.21729v1
- Date: Wed, 31 Jul 2024 16:30:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-01 17:31:11.961571
- Title: ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization
- Title（参考訳）: ParLS-PBO:擬似ブール最適化のための並列局所探索法
- Authors: Zhihan Chen, Peng Lin, Hao Hu, Shaowei Cai,
- Abstract要約: PBOの代表的なローカルサーチソルバはLSPBOである。
動的スコアリング機構によりLSPBOを改良し、ハード制約のスコアと目標関数のスコアのバランスを動的に調整する。
この改良されたLSPBOの上に,最初の並列局所探索PBOソルバを開発した。
- 参考スコア（独自算出の注目度）: 14.371138535749036
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LSPBO. In this paper, firstly, we improve LSPBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. Moreover, on top of this improved LSPBO , we develop the first parallel local search PBO solver. The main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi.
- Abstract（参考訳）: 近年,多くの最適化問題において広く応用されている手法として,PBO(Pseudo-Boolean Optimization)問題の解法として局所探索が採用されている。
PBOの代表的なローカルサーチソルバはLSPBOである。
本稿では,まず,動的スコアリング機構によりLSPBOを改良し,ハード制約のスコアと目標関数のスコアのバランスを動的に決定する。
さらに、この改良されたLSPBOを用いて、最初の並列ローカル検索PBOソルバを開発する。
主なアイデアは、実現可能なソリューションのプールを維持することによって、検索をガイドするために、異なるスレッド間で優れたソリューションを共有することである。
プールを更新する際の解を評価するために,プールの品質とプールの多様性を両立する関数を提案する。
さらに,プール内の極性密度を算出し,局所探索のスコアリング機能を強化する。
我々の実証実験は、提案した並列手法の利点を明らかに示しており、有名な商用解法であるGurobiの並列バージョンと競合する。
関連論文リスト
- A Random-Key Optimizer for Combinatorial Optimization [0.0]
Random-Key Hubs (RKO) は最適化問題に適した汎用的で効率的な局所探索手法である。
ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に問題固有のデコーダを介して実現可能な解へとデコードする。
RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
論文 参考訳（メタデータ） (2024-11-06T22:23:29Z) - Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - 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) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming [3.759879849096294]
ASP(Answer Set Programming)における最適化問題に対するLNPS(Large Neighborhood Prioritized Search)を提案する。
LNPSはメタヒューリスティックであり、初期解から始まり、次に現在の解の探索を交互に破壊し優先順位付けすることでより良い解を見つけようとする。
本稿では,ASP に基づく LNPS の実装について述べる。その結果,LNPS が ASP の最適化性能を大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2024-05-18T14:37:43Z) - Poisson Process for Bayesian Optimization [126.51200593377739]
本稿では、Poissonプロセスに基づくランキングベースの代理モデルを提案し、Poisson Process Bayesian Optimization(PoPBO)と呼ばれる効率的なBOフレームワークを提案する。
従来のGP-BO法と比較すると,PoPBOはコストが低く,騒音に対する堅牢性も良好であり,十分な実験により検証できる。
論文 参考訳（メタデータ） (2024-02-05T02:54:50Z) - Evidence that PUBO outperforms QUBO when solving continuous optimization
problems with the QAOA [4.670374869377859]
量子アルゴリズムによる最適化問題の解決における中核的なステップは、問題の定式化である。
近年の研究では、多くの問題を自然の多項式非制約最適化形式でより効率的に解けることが示されている。
適切なベンチマーク関数の評価では、PUBOの定式化は一般により良い結果をもたらすが、キュービットは少ない。
論文 参考訳（メタデータ） (2023-05-05T09:37:48Z) - DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean
Optimization [10.513103815142731]
PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。
我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
論文 参考訳（メタデータ） (2023-01-28T17:03:56Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳（メタデータ） (2023-01-24T12:01:45Z) - A Bayesian Optimization Framework for Finding Local Optima in Expensive
Multi-Modal Functions [18.570591025615453]
本稿では,高コストで評価可能なマルチモーダル目的関数に対する局所的・言語的ソリューションの集合を見つけるためのマルチモーダルBOフレームワークを開発する。
目的関数とその一階微分の結合分布を解析的に導出する。
本稿では、マルチモーダル設定によく知られたBO取得関数の変種を導入し、提案フレームワークの性能を実証する。
論文 参考訳（メタデータ） (2022-10-13T00:10:13Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。