論文の概要: Anytime Cooperative Implicit Hitting Set Solving

• arxiv url: http://arxiv.org/abs/2501.07896v1
• Date: Tue, 14 Jan 2025 07:23:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-15 13:25:27.648792
• Title: Anytime Cooperative Implicit Hitting Set Solving
• Title（参考訳）: いつでも協力的意図的ハッティング・セットの解決
• Authors: Emma Rollón, Javier Larrosa, Aleksandra Petrova,
• Abstract要約: Implicit Hitting Set (HS)アプローチは、MaxSAT、Pseudo-boolean最適化、その他のフレームワークに非常に効果的であることが示されている。 いずれのコンポーネントによって発見されたコアが利用できるマルチスレッドアーキテクチャにおいて、どのように簡単に組み合わせられるかを示す。 その結果,HS-lub は HS-lb と HS-ub のどちらよりも独立に優れていることがわかった。
• 参考スコア（独自算出の注目度）: 46.010796136659536
• License:
• Abstract: The Implicit Hitting Set (HS) approach has shown to be very effective for MaxSAT, Pseudo-boolean optimization and other boolean frameworks. Very recently, it has also shown its potential in the very similar Weighted CSP framework by means of the so-called cost-function merging. The original formulation of the HS approach focuses on obtaining increasingly better lower bounds (HS-lb). However, and as shown for Pseudo-Boolean Optimization, this approach can also be adapted to compute increasingly better upper bounds (HS-ub). In this paper we consider both HS approaches and show how they can be easily combined in a multithread architecture where cores discovered by either component are available by the other which, interestingly, generates synergy between them. We show that the resulting algorithm (HS-lub) is consistently superior to either HS-lb and HS-ub in isolation. Most importantly, HS-lub has an effective anytime behaviour with which the optimality gap is reduced during the execution. We tested our approach on the Weighted CSP framework and show on three different benchmarks that our very simple implementation sometimes outperforms the parallel hybrid best-first search implementation of the far more developed state-of-the-art Toulbar2.
• Abstract（参考訳）: Implicit Hitting Set (HS) アプローチは、MaxSAT、Pseudo-boolean最適化、その他のブールフレームワークに非常に効果的であることが示されている。 最近では、いわゆるコスト関数のマージによって、非常に類似したWeighted CSPフレームワークの可能性も示している。 HSアプローチの元々の定式化は、より優れた下界(HS-lb)を得ることに焦点を当てている。 しかし、Pseudo-Boolean Optimizationで示されているように、このアプローチはより優れた上限(HS-ub)を計算するために適応することもできる。 本稿では,HS と HS の両アプローチについて考察し,両コンポーネントが検出したコアを相互に利用可能なマルチスレッドアーキテクチャで組み合わせる方法について述べる。 その結果,HS-lub は HS-lb と HS-ub のどちらよりも独立に優れていることがわかった。 最も重要なことは、HS-lubは、実行中に最適性ギャップが減少する効果的な任意の動作を有することである。 我々は、Weighted CSPフレームワークのアプローチを検証し、3つの異なるベンチマークで、我々の非常に単純な実装は、より先進的なToulbar2の並列ハイブリッド検索実装よりも優れていることを示す。

関連論文リスト

• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs [46.010796136659536]
  重み付きCSP問題に対する既存の参照アルゴリズムの代替策について検討する。 我々の実証研究は、WCSPにとって最良の選択肢を特定するのは容易ではないことを示している。
  論文  参考訳（メタデータ） (2025-01-13T15:59:28Z)
• 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)
• CEBin: A Cost-Effective Framework for Large-Scale Binary Code Similarity Detection [23.8834126695488]
  バイナリコード類似度検出(BCSD)は様々なアプリケーションの基本技術である。 本稿では,組込み型および比較型アプローチを融合した,費用対効果の高いBCSDフレームワークCEBinを提案する。
  論文  参考訳（メタデータ） (2024-02-29T03:02:07Z)
• FlexHB: a More Efficient and Flexible Framework for Hyperparameter Optimization [4.127081624438282]
  連続的Halving(SH)による早期停止のためのフレームワークを設計し,その限界に多要素BOをプッシュする新しい手法であるFlexHBを提案する。 提案手法は,様々なHPOタスクにおいて,優れた効率性を実現し,他の手法よりも優れる。
  論文  参考訳（メタデータ） (2024-02-21T09:18:59Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。 この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
  論文  参考訳（メタデータ） (2021-07-27T08:48:01Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Comparing and Combining Approximate Computing Frameworks [0.0]
  VIPERとBOAは、より大きくよりリッチなトレードオフ空間を作るために、近似フレームワークをどのように比較して組み合わせるかを示している。 VIPERとBOAを使用して、システムスタック全体から3つの異なる近似フレームワークを比較し、組み合わせます。
  論文  参考訳（メタデータ） (2021-02-16T04:52:43Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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