論文の概要: Half-checking propagators

• arxiv url: http://arxiv.org/abs/2007.05423v1
• Date: Fri, 10 Jul 2020 14:54:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-11 21:58:55.285411
• Title: Half-checking propagators
• Title（参考訳）: 半検査プロパゲータ
• Authors: Mikael Zayenz Lagerkvist and Magnus Rattfeldt
• Abstract要約: プロパゲータは、与えられた制約のどの解にも属さないことが証明された値を削除する。 半チェックプロパゲータが導入されたが、特定のソリューションが実際のソリューションであるという唯一の要件がある。 ポートフォリオ解決プロセスの1つのコンポーネントとして半チェックプロパゲータを実行することで、全体的な完全性を得ることができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Propagators are central to the success of constraint programming, that is contracting functions removing values proven not to be in any solution of a given constraint. The literature contains numerous propagation algorithms, for many different constraints, and common to all these propagation algorithms is the notion of correctness: only values that appear in no solution to the respective constraint may be removed. In this paper half-checking propagators are introduced, for which the only requirements are that identified solutions (by the propagators) are actual solutions (to the corresponding constraints), and that the propagators are contracting. In particular, a half-checking propagator may remove solutions resulting in an incomplete solving process, but with the upside that (good) solutions may be found faster. Overall completeness can be obtained by running half-checking propagators as one component in a portfolio solving process. Half-checking propagators opens up a wider variety of techniques to be used when designing propagation algorithms, compared to what is currently available. A formal model for half-checking propagators is introduced, together with a detailed description of how to support such propagators in a constraint programming system. Three general directions for creating half-checking propagation algorithms are introduced, and used for designing new half-checking propagators for the cost-circuit constraint as examples. The new propagators are implemented in the Gecode system.
• Abstract（参考訳）: プロパゲータは制約プログラミングの成功の中心であり、与えられた制約の解でないことが証明された値を取り除く関数を縮めている。 文献には、多くの異なる制約のために、多くの伝播アルゴリズムが含まれており、これらすべての伝播アルゴリズムに共通するのは、正しさの概念である。 本稿では, (プロパゲータによる)特定解が(対応する制約に対する)実際の解であること, および, プロパゲータが契約していることを条件として, 半チェックプロパゲータを導入する。 特に、半チェックプロパゲータは、不完全な解決プロセスをもたらす解を取り除くかもしれないが、(良い)解がより早く見つかるという利点がある。 ポートフォリオ解決プロセスの1つのコンポーネントとして半チェックプロパゲータを実行することで、全体的な完全性を得ることができる。 半チェックプロパゲータは、現在利用可能なものと比較して、伝播アルゴリズムを設計する際に使用される幅広いテクニックを開放する。 半チェックプロパゲータの形式モデルを導入し、制約プログラミングシステムにおいてそのようなプロパゲータをサポートする方法について詳述する。 半チェック伝搬アルゴリズムを作成するための3つの一般的な方向を導入し、コスト回路制約に対する新しい半チェックプロパゲータを例として用いた。 新しいプロパゲータはgecodeシステムに実装されている。

関連論文リスト

• Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
  量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。 量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。 本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
  論文  参考訳（メタデータ） (2023-10-08T08:07:11Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。 MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。 本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
  論文  参考訳（メタデータ） (2022-08-11T10:31:28Z)
• Cooperative Distribution Alignment via JSD Upper Bound [7.071749623370137]
  教師なし分布アライメントは、2つ以上のソース分布を共有整列分布にマッピングする変換を推定する。 このタスクには、生成モデリング、教師なしドメイン適応、社会的に認識された学習など、多くの応用がある。 我々は,従来のフローベースアプローチを,単一の非逆数フレームワークで統一し,一般化することを提案する。
  論文  参考訳（メタデータ） (2022-07-05T20:09:03Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Iterative Pre-Conditioning to Expedite the Gradient-Descent Method [0.966840768820136]
  本稿では,マルチエージェント分散最適化の問題について考察する。 そこで本研究では,勾配差分法による収束速度に対する問題条件付けの影響を大幅に軽減できる反復的事前条件付け手法を提案する。
  論文  参考訳（メタデータ） (2020-03-13T16:30:01Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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