論文の概要: A Linear Weight Transfer Rule for Local Search
- arxiv url: http://arxiv.org/abs/2303.14894v1
- Date: Mon, 27 Mar 2023 03:06:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-28 16:54:59.109246
- Title: A Linear Weight Transfer Rule for Local Search
- Title（参考訳）: 局所探索のための線形重み移動規則
- Authors: Md Solimul Chowdhury and Cayden R. Codel and Marijn J.H. Heule
- Abstract要約: Divide and Distribute Fixed Weights algorithm (ddfw) は、局所最小値において、満足度から偽値に重みを移す動的局所探索SAT解決アルゴリズムである。
本稿では,局所ミニマにおける節間の動的重みを移動させる線形重み移動法,局所ミニマにおいて満足節をどのように選択して重みを与えるかの調整,およびフリップする変数を選択する重み付きランダム法という3つの基本アルゴリズムの修正を提案する。
- 参考スコア（独自算出の注目度）: 5.414308305392761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Divide and Distribute Fixed Weights algorithm (ddfw) is a dynamic local
search SAT-solving algorithm that transfers weight from satisfied to falsified
clauses in local minima. ddfw is remarkably effective on several hard
combinatorial instances. Yet, despite its success, it has received little study
since its debut in 2005. In this paper, we propose three modifications to the
base algorithm: a linear weight transfer method that moves a dynamic amount of
weight between clauses in local minima, an adjustment to how satisfied clauses
are chosen in local minima to give weight, and a weighted-random method of
selecting variables to flip. We implemented our modifications to ddfw on top of
the solver yalsat. Our experiments show that our modifications boost the
performance compared to the original ddfw algorithm on multiple benchmarks,
including those from the past three years of SAT competitions. Moreover, our
improved solver exclusively solves hard combinatorial instances that refute a
conjecture on the lower bound of two Van der Waerden numbers set forth by Ahmed
et al. (2014), and it performs well on a hard graph-coloring instance that has
been open for over three decades.
- Abstract（参考訳）: 分割分散固定重みアルゴリズム (ddfw) は、局所的ミニマにおける重みを満足度から偽化節へ転送する動的局所探索sat解決アルゴリズムである。
ddfwはいくつかのハードコンビネートインスタンスで非常に効果的である。
しかし、その成功にもかかわらず、2005年のデビュー以来ほとんど研究を受けていない。
本稿では,局所ミニマにおける節間の動的重みを移動させる線形重み移動法,局所ミニマにおいて満足節をどのように選択して重みを与えるかの調整,およびフリップする変数を選択する重み付きランダム法という3つの基本アルゴリズムの修正を提案する。
我々はddfwの修正をソルバyalsat上に実装した。
本実験は,過去3年間のSATコンペティションを含む複数のベンチマークにおいて,従来のddfwアルゴリズムと比較して性能が向上したことを示す。
さらに、改良された解法は、Ahmed et al. (2014) の2つのファンデルワーデン数の下界での予想を反論するハードコンビナトリのインスタンスを排他的に解き、30年以上開き続けているハードグラフカラーのインスタンスでうまく機能する。
関連論文リスト
- A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - A Scalable Second Order Method for Ill-Conditioned Matrix Completion
from Few Samples [0.0]
低ランク行列補完のための反復アルゴリズムを提案する。
ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
論文 参考訳（メタデータ） (2021-06-03T20:31:00Z) - Rejection sampling from shape-constrained distributions in sublinear
time [14.18847457501901]
離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。
本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-29T01:00:42Z) - Escaping Saddle Points in Distributed Newton's Method with Communication
efficiency and Byzantine Resilience [49.379254729853756]
我々は、ビザンチン機械の存在下で分散フレームワークにおける非正規化損失関数(サドルポイント付き)を最適化する問題を検討する。
キューブ正規化されたニュートンアルゴリズムを堅牢化し、サドルポイントと偽のローカルミニマを効率的に回避します。
提案手法は, (サブサンプリング) と hessian を含むいくつかの近似設定で理論的に保証される。
論文 参考訳（メタデータ） (2021-03-17T03:53:58Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Escaping Saddle Points in Ill-Conditioned Matrix Completion with a
Scalable Second Order Method [0.0]
低ランク行列に対する反復アルゴリズムを提案する。
多くの最先端の手法とは異なり、我々の手法は少数のサンプルから最大10ドルの条件数で非常に不調な条件を満たすことができることを示す数値実験で示している。
論文 参考訳（メタデータ） (2020-09-07T06:51:20Z) - Approximating a Target Distribution using Weight Queries [25.392248158616862]
本稿では,データセットの例を反復的に選択し,対応する重み付けクエリを実行する対話型アルゴリズムを提案する。
我々は,アルゴリズムが検出した再重み付けと,最も達成可能な再重み付けとの間の全変動距離に依存する近似を導出する。
論文 参考訳（メタデータ） (2020-06-24T11:17:43Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。