論文の概要: GPU Accelerated Compact-Table Propagation

• arxiv url: http://arxiv.org/abs/2507.18413v1
• Date: Thu, 24 Jul 2025 13:53:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-25 15:10:43.73036
• Title: GPU Accelerated Compact-Table Propagation
• Title（参考訳）: GPUアクセラレーションによる小型テーブルの伝搬
• Authors: Enrico Santi, Fabio Tardivo, Agostino Dovier, Andrea Formisano,
• Abstract要約: この研究は、変数の値の条件を代替オプションの列挙として指定するために使われる、テーブル制約と呼ばれる特定の形式の制約に焦点を当てる。 有限領域変数の集合上のすべての条件は最終的に有限ケースの集合として表現できるので、テーブルは他の制約をシミュレートすることができる。 本稿では,テーブルの最先端の伝搬アルゴリズムであるCT(Compact-Table)アルゴリズムについて述べる。
• 参考スコア（独自算出の注目度）: 1.7249361224827533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint Programming developed within Logic Programming in the Eighties; nowadays all Prolog systems encompass modules capable of handling constraint programming on finite domains demanding their solution to a constraint solver. This work focuses on a specific form of constraint, the so-called table constraint, used to specify conditions on the values of variables as an enumeration of alternative options. Since every condition on a set of finite domain variables can be ultimately expressed as a finite set of cases, Table can, in principle, simulate any other constraint. These characteristics make Table one of the most studied constraints ever, leading to a series of increasingly efficient propagation algorithms. Despite this, it is not uncommon to encounter real-world problems with hundreds or thousands of valid cases that are simply too many to be handled effectively with standard CPU-based approaches. In this paper, we deal with the Compact-Table (CT) algorithm, the state-of-the-art propagation algorithms for Table. We describe how CT can be enhanced by exploiting the massive computational power offered by modern GPUs to handle large Table constraints. In particular, we report on the design and implementation of GPU-accelerated CT, on its integration into an existing constraint solver, and on an experimental validation performed on a significant set of instances.
• Abstract（参考訳）: 論理プログラミングにおける制約プログラミングは、現代では全てのPrologシステムは、制約解法に解を求める有限領域上の制約プログラミングを処理できるモジュールを含んでいる。 この研究は、変数の値に関する条件を代替オプションの列挙として指定するために使われる、テーブル制約と呼ばれる特定の形式の制約に焦点を当てる。 有限領域変数の集合上のすべての条件は最終的に有限ケースの集合として表現できるので、テーブルは他の制約をシミュレートすることができる。 これらの特徴は、Tableをこれまでで最も研究された制約の一つにし、より効率的な伝播アルゴリズムのシリーズに繋がる。 それにもかかわらず、数百から数千の有効なケースで現実の問題に遭遇することは珍しくなく、単に多くのケースが標準のCPUベースのアプローチで効果的に処理できない。 本稿では,テーブルの最先端の伝搬アルゴリズムであるCT(Compact-Table)アルゴリズムについて述べる。 本稿では,最近のGPUの計算能力を利用して,大規模テーブル制約に対処することにより,CTの強化を実現する方法について述べる。 特に,GPUアクセラレーションCTの設計と実装,既存の制約解決器への統合,および多数のインスタンス上で実施された実験的検証について報告する。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Generalizing Constraint Models in Constraint Acquisition [6.305123652677644]
  制約獲得(CA:Constraint Acquisition)は、モデリングプロセスにおいてユーザを支援することによって制約プログラミングの利用を拡大することを目的としている。 多くのCAメソッドは、特定の問題インスタンスに対して1組の個々の制約を学習するが、これらの制約を問題のパラメータ化された制約仕様に一般化することはできない。 我々は、同じ問題の様々なインスタンスをモデル化できるパラメータ化制約モデルを学ぶための新しい手法GenConを提案する。
  論文  参考訳（メタデータ） (2024-12-19T15:31:29Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  本稿では,ロボット推論と計画における連続的制約満足度問題(CCSP)の解法について紹介する。 対照的に、構成拡散連続制約解法(Diffusion-CCSP)は、CCSPに対する大域的な解を導出する。
  論文  参考訳（メタデータ） (2023-09-02T15:20:36Z)
• ACE, a generic constraint solver [1.550120821358415]
  制約プログラミング(CP)は制約された問題のモデリングと解決に有用な技術である。 本稿では,Javaで開発されたオープンソースの制約解決ツールACEについて述べる。
  論文  参考訳（メタデータ） (2023-01-06T12:15:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints [0.0]
  表の制約はおそらく最も重要であり、最もよく研究され、有限変数上で定義された他の制約をエンコードする能力を持つ。 空間と時間の複雑さを減らすために、研究者は様々な種類の圧縮に焦点を当ててきた。 本稿では,テーブル制約の圧縮に関連する最大頻繁な項目セットを列挙するための,最大頻繁な項目セット手法と面積尺度に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2022-03-21T08:41:15Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)

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

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