論文の概要: An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques

• arxiv url: http://arxiv.org/abs/2509.13880v1
• Date: Wed, 17 Sep 2025 10:19:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 18:41:50.820778
• Title: An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques
• Title（参考訳）: 簡易化手法を用いた整数線形制約を用いたDPLLによるモデルカウント
• Authors: Mingwei Zhang, Zhenhao Gu, Liangda Fang, Cunjing Ge, Ziliang Chen, Zhao-Rong Lai, Quanlong Guan,
• Abstract要約: 本稿では, DPLL アーキテクチャに基づく MCILC への正確なアプローチを設計する。 我々は、2840のランダムおよび4131のアプリケーションベンチマーク上で、最先端のMCILCカウンタと命題モデルカウンタとの比較を行った。
• 参考スコア（独自算出の注目度）: 26.55400038540141
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear constraints are one of the most fundamental constraints in fields such as computer science, operations research and optimization. Many applications reduce to the task of model counting over integer linear constraints (MCILC). In this paper, we design an exact approach to MCILC based on an exhaustive DPLL architecture. To improve the efficiency, we integrate several effective simplification techniques from mixed integer programming into the architecture. We compare our approach to state-of-the-art MCILC counters and propositional model counters on 2840 random and 4131 application benchmarks. Experimental results show that our approach significantly outperforms all exact methods in random benchmarks solving 1718 instances while the state-of-the-art approach only computes 1470 instances. In addition, our approach is the only approach to solve all 4131 application instances.
• Abstract（参考訳）: 線形制約は、コンピュータ科学、操作研究、最適化といった分野における最も基本的な制約の1つである。 多くのアプリケーションは、整数線形制約(MCILC)よりもモデルカウントのタスクに還元される。 本稿では, DPLL アーキテクチャに基づく MCILC への正確なアプローチを設計する。 効率を向上させるために、混合整数プログラミングからいくつかの効果的な単純化手法をアーキテクチャに統合する。 我々は、2840のランダムおよび4131のアプリケーションベンチマーク上で、最先端のMCILCカウンタと命題モデルカウンタとの比較を行った。 実験の結果,提案手法は1718のインスタンスを探索するランダムベンチマークにおいて,1470のインスタンスのみを計算するのに対して,精度が著しく向上していることが判明した。 さらに、このアプローチは、4131のアプリケーションインスタンスをすべて解決するための唯一のアプローチです。

関連論文リスト

• Pareto Multi-Objective Alignment for Language Models [7.9051473654430655]
  大規模言語モデル(LLM)は、複数の、しばしば矛盾する、目的の慎重なバランスを必要とする現実世界のアプリケーションに、ますます多くデプロイされている。 LLMにおける多目的アライメント(MOA)を明示的に設計するアルゴリズムを提案する。 PAMAは、マルチオブジェクトRLHFをクローズドフォームソリューションで凸最適化に変換し、スケーラビリティを大幅に向上させる。
  論文  参考訳（メタデータ） (2025-08-11T08:54:14Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Exact and general decoupled solutions of the LMC Multitask Gaussian Process model [28.32223907511862]
  コリージョン化線形モデル(英: Linear Model of Co- Regionalization、LMC)は、回帰や分類のためのマルチタスクガウス過程の非常に一般的なモデルである。 最近の研究によると、ある条件下では、モデルの潜在過程は切り離され、そのプロセスの数でのみ線形となる複雑さが生じる。 ここでは、これらの結果を拡張し、LCCの効率的な正確な計算に必要な条件はノイズモデルに関する軽度の仮説である、という最も一般的な仮定から示している。
  論文  参考訳（メタデータ） (2023-10-18T15:16:24Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  モデルベースRL(MBRL)の非遅延性能保証のための新規で一般的な理論スキームを提案する。 続いて導いた境界は、モデルシフトとパフォーマンス改善の関係を明らかにします。 さらなる例では、動的に変化する探索からの学習モデルが、最終的なリターンの恩恵をもたらすことが示されている。
  論文  参考訳（メタデータ） (2022-10-15T17:57:43Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  多目的最適化(MOCO)の問題は、現実世界の多くのアプリケーションで見られる。 我々は,与えられたMOCO問題に対するパレート集合全体を,探索手順を伴わずに近似する学習ベースアプローチを開発した。 提案手法は,多目的走行セールスマン問題,マルチコンディショニング車両ルーティング問題,複数クナップサック問題において,ソリューションの品質,速度,モデル効率の面で,他の方法よりも優れていた。
  論文  参考訳（メタデータ） (2022-03-29T09:26:22Z)
• Conservative Objective Models for Effective Offline Model-Based Optimization [78.19085445065845]
  計算設計の問題は、合成生物学からコンピュータアーキテクチャまで、様々な場面で発生している。 本研究では,分布外入力に対する接地的目標の実際の値を低くする目的関数のモデルを学習する手法を提案する。 COMは、様々なMBO問題に対して、既存のメソッドの実装と性能の面では単純である。
  論文  参考訳（メタデータ） (2021-07-14T17:55:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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