論文の概要: On Weakening Strategies for PB Solvers

• arxiv url: http://arxiv.org/abs/2005.04466v1
• Date: Sat, 9 May 2020 15:40:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-05 07:01:57.037274
• Title: On Weakening Strategies for PB Solvers
• Title（参考訳）: pbソルバの弱化戦略について
• Authors: Daniel Le Berre, Pierre Marquis, Romain Wallon
• Abstract要約: 現在の擬ブール解法は、競合解析中に新しい制約を推測するために切断平面証明システムの異なる変種を実装している。 これらの変種の一つは一般化分解であり、強い制約を推測することができるが、それが生成する係数の増大に悩まされる。 別の変種は弱化と除算を使い、実際はより効率的だがより弱い制約を推測する。
• 参考スコア（独自算出の注目度）: 19.78156213005998
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current pseudo-Boolean solvers implement different variants of the cutting planes proof system to infer new constraints during conflict analysis. One of these variants is generalized resolution, which allows to infer strong constraints, but suffers from the growth of coefficients it generates while combining pseudo-Boolean constraints. Another variant consists in using weakening and division, which is more efficient in practice but may infer weaker constraints. In both cases, weakening is mandatory to derive conflicting constraints. However, its impact on the performance of pseudo-Boolean solvers has not been assessed so far. In this paper, new application strategies for this rule are studied, aiming to infer strong constraints with small coefficients. We implemented them in Sat4j and observed that each of them improves the runtime of the solver. While none of them performs better than the others on all benchmarks, applying weakening on the conflict side has surprising good performance, whereas applying partial weakening and division on both the conflict and the reason sides provides the best results overall.
• Abstract（参考訳）: 現在の擬ブール解法は、競合解析中に新しい制約を推測するために切断平面証明システムの異なる変種を実装している。 これらの変種の一つは一般化分解であり、強い制約を推測することができるが、擬似ブーリアン制約を組み合わせながら生成する係数の成長に苦しむ。 別の変種は弱化と除算を使い、実際にはより効率的であるがより弱い制約を推測する。 どちらの場合も、弱体化は矛盾する制約を導き出すために必須である。 しかし,pseudo-booleanソルバの性能への影響は今のところ評価されていない。 本稿では,このルールに対する新しい適用戦略について検討し,小さい係数で強い制約を推測することを目的とした。 Sat4jで実装し、それぞれがソルバのランタイムを改善していることを観察しました。 いずれのベンチマークも他のベンチマークよりもパフォーマンスは良くないが、コンフリクト側で弱体化を適用すると驚くべきパフォーマンスを示す一方、コンフリクト側と理由側の両方で部分弱体化と分割を適用すると、全体として最高の結果が得られる。

関連論文リスト

• Temporal Elections: Welfare, Strategyproofness, and Proportionality [21.36300710262896]
  我々は、実用的福祉(Util)と平等的福祉(Egal)の2つの目的に焦点を当て、関連する問題の計算複雑性を考察する。 我々は、Util の最大化は容易であるが、Egal の対応する決定問題は制限された場合においてもNP完全であると考えている。
  論文  参考訳（メタデータ） (2024-08-24T17:52:26Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
  本稿では,ユーザが特定した攻撃モデルに対して最適に堅牢な決定木を訓練する手法の集合を提案する。 逆学習において生じるmin-max最適化問題は、単一最小化定式化を用いて解くことができることを示す。 また,両部マッチングを用いた任意のモデルに対して,上界の対角精度を決定する手法を提案する。
  論文  参考訳（メタデータ） (2021-09-08T18:10:49Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Batched Neural Bandits [107.5072688105936]
  BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。 BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
  論文  参考訳（メタデータ） (2021-02-25T17:36:44Z)
• On Irrelevant Literals in Pseudo-Boolean Constraint Learning [21.506382989223784]
  関連するリテラルが、本来よりも弱い制約を推論する可能性があることを示す。 これは、切断平面に基づくpbソルバの現在の実装は、無関係リテラルの発生を防止するために再検討されるべきであることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T13:52:09Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。 我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
  論文  参考訳（メタデータ） (2020-02-08T19:35:01Z)

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

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