論文の概要: 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の並列バージョンと競合する。
関連論文リスト
- 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) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳(メタデータ) (2023-12-26T03:09:08Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - 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) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳(メタデータ) (2021-07-27T08:48:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。