論文の概要: Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach

• arxiv url: http://arxiv.org/abs/2508.07015v1
• Date: Sat, 09 Aug 2025 15:27:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.654462
• Title: Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach
• Title（参考訳）: インシシット・ハッティング・セット・アプローチのための効率的かつ信頼性の高いハッティング・セット・計算法
• Authors: Hannes Ihalainen, Dieter Vandesande, André Schidler, Jeremias Berg, Bart Bogaerts, Matti Järvisalo,
• Abstract要約: 暗黙的なヒットセット(IHS)アプローチは、計算的にハードな最適化問題を解決するための一般的なフレームワークを提供する。 我々は、擬似ブール推論(PB)を用いた様々な手法に基づいて、集合最適化を打つための代替アルゴリズムについて検討する。 PB推論によってインスタンス化された正確なHS計算は、数値的に正確なIPソルバと競合できることを示す。
• 参考スコア（独自算出の注目度）: 11.039737232955039
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The implicit hitting set (IHS) approach offers a general framework for solving computationally hard combinatorial optimization problems declaratively. IHS iterates between a decision oracle used for extracting sources of inconsistency and an optimizer for computing so-called hitting sets (HSs) over the accumulated sources of inconsistency. While the decision oracle is language-specific, the optimizers is usually instantiated through integer programming. We explore alternative algorithmic techniques for hitting set optimization based on different ways of employing pseudo-Boolean (PB) reasoning as well as stochastic local search. We extensively evaluate the practical feasibility of the alternatives in particular in the context of pseudo-Boolean (0-1 IP) optimization as one of the most recent instantiations of IHS. Highlighting a trade-off between efficiency and reliability, while a commercial IP solver turns out to remain the most effective way to instantiate HS computations, it can cause correctness issues due to numerical instability; in fact, we show that exact HS computations instantiated via PB reasoning can be made competitive with a numerically exact IP solver. Furthermore, the use of PB reasoning as a basis for HS computations allows for obtaining certificates for the correctness of IHS computations, generally applicable to any IHS instantiation in which reasoning in the declarative language at hand can be captured in the PB-based proof format we employ.
• Abstract（参考訳）: 暗黙的なヒットセット(IHS)アプローチは、計算的に難しい組合せ最適化問題を宣言的に解くための一般的なフレームワークを提供する。 IHSは、不整合のソースを抽出するために使われる決定オラクルと、蓄積された不整合のソースに対していわゆるヒットセット(HS)を計算するための最適化器を繰り返す。 決定オラクルは言語固有のものであるが、オプティマイザは通常整数プログラミングによってインスタンス化される。 本稿では,擬似ブール推論(PB)と確率的局所探索の異なる手法を用いて,集合最適化を打つアルゴリズムを提案する。 IHSの最近のインスタンス化の1つとして、疑似ブール(0-1 IP)最適化の文脈において、代替案の実用可能性について広範囲に評価した。 効率性と信頼性のトレードオフを強調させる一方で、商用IPソルバは、HS計算をインスタンス化する最も効果的な方法でありながら、数値不安定性による正確性の問題を引き起こす可能性がある。 さらに, PB推論をベースとして, IHS計算の正しさの証明を得ることが可能であり, 宣言型言語での推論をPBベースの証明形式で捉えることができるような, IHSのインスタンス化に適用できる。

関連論文リスト

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• 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)
• Robust expected improvement for Bayesian optimization [1.8130068086063336]
  本稿では,BO/GPフレームワークに敵対的手法を組み込む,堅牢な予測改善(REI)と呼ばれる代理モデルとアクティブラーニング手法を提案する。 ベンチマーク・シンセティック・エクササイズと、様々な複雑さの実際の問題について、いくつかの競合相手と比較し、比較する。
  論文  参考訳（メタデータ） (2023-02-16T22:34:28Z)
• Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality [31.359578768463752]
  本稿では,固定信頼設定における多腕バンディットにおけるベストアーム識別(BAI)の非装飾的側面について検討する。 帯域幅アルゴリズムを評価するための2つの重要な指標は、計算効率と性能最適性である。 本稿では,BAIのためのフレームワークとアルゴリズムを導入し,計算効率のよい決定ルールセットを用いて最適性能を実現する。
  論文  参考訳（メタデータ） (2023-01-10T05:02:49Z)
• Enhancing Explainability of Hyperparameter Optimization via Bayesian Algorithm Execution [13.037647287689438]
  部分依存プロットのような解釈可能な機械学習(IML)手法とHPOの組み合わせについて検討する。 我々は,最適大域的予測性能を効率的に探索する改良HPO法を提案する。 提案手法は,最適化性能を損なうことなく,ブラックボックスの信頼性の高い説明を返す。
  論文  参考訳（メタデータ） (2022-06-11T07:12:04Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。 余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。 提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
  論文  参考訳（メタデータ） (2020-12-02T12:04:16Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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