論文の概要: Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
- arxiv url: http://arxiv.org/abs/2608.15143v1
- Date: Sat, 15 Aug 2026 09:38:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.208926
- Title: Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
- Title（参考訳）: CPMpyを用いた有限領域整数制約モデルのCP/SMT/ILP/PB/SATソルバへの変換
- Abstract要約: 制約解決は満足度と最適化問題を解決するための宣言的アプローチである。
我々のゴールは、高いレベルの制約満足度と最適化問題を低レベルの形式に翻訳することです。
本稿では、高レベルモデリング言語をCP/SMT/ILP/PBおよび(Max)SATソルバに変換するためのモジュラーフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 6.498850269638911
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constraint solving is a declarative approach for solving combinatorial satisfaction and optimization problems. The user specifies their problem through constraints and decision variables, and a generic solver is used to find a solution. Several constraint-solving technologies exist, and certain solvers perform well on certain problems. Therefore, it is useful to try different solvers given a particular application. However, each solving paradigm supports different types of constraints and decision variables. Our goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism, including CP, SMT QF-LIA, ILP, PB and (Max)SAT. This allows for comparing different solving technologies for a particular problem, without requiring a user to manually remodel it for each solving paradigm. We define a high-level language of logical and arithmetic operations, and useful additional functions and constraints, which are known as global constraints in the CP community. We then present a modular framework for transforming our high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers. While many transformations are partly described in the literature, we observe that they can be implemented through a modular waterfall of smaller components, where lower-level paradigms reuse the transformations of higher-level paradigms. Two recurring challenges are handling the negation of arbitrary subexpressions and avoiding the introduction of auxiliary variables. Additionally, we take special care linearizing non-linear operators for ILP, PB and SAT-solvers. The transformation waterfall is implemented and evaluated in the open-source CPMpy library. Our results show that constraint models significantly change throughout the transformations, and that optimizations to the linearization of constraints are essential for ILP and PB solvers.
- Abstract（参考訳）: 制約解決は組合せ満足度と最適化問題を解決するための宣言的アプローチである。
ユーザは制約や決定変数を通じて問題を指定し、ジェネリックソルバを使用して解決策を見つける。
いくつかの制約解決技術が存在し、ある解法は特定の問題に対してよく機能する。
したがって、特定の応用に対して異なる解法を試すことは有用である。
しかし、それぞれの解法パラダイムは、異なるタイプの制約と決定変数をサポートしている。
我々の目標は、CP, SMT QF-LIA, ILP, PB, (Max)SATなど、高レベルの制約満足度と最適化問題を下層形式に翻訳することである。
これにより、ユーザが各問題解決パラダイムに対して手動でリモデリングする必要がなく、特定の問題に対して異なる問題解決技術を比較することができる。
我々は、論理演算と算術演算の高レベル言語を定義し、CPコミュニティのグローバル制約として知られる有用な追加関数と制約を定義した。
次に、高レベルモデリング言語をCP/SMT/ILP/PBおよび(Max)SATソルバに変換するためのモジュラーフレームワークを提案する。
多くの変換が文献で部分的に説明されているが、低レベルのパラダイムが高レベルのパラダイムの変換を再利用する、より小さなコンポーネントのモジュラーウォーターフォールを通じて実装できることが観察されている。
繰り返し発生する2つの課題は、任意の部分表現の否定に対処し、補助変数の導入を避けることである。
さらに, ILP, PB, SAT-solverの非線形演算子を特別に線形化する。
トランスフォーメーションのウォーターフォールは、オープンソースのCPMpyライブラリで実装され、評価されている。
以上の結果から,制約モデルが変換全体を通して著しく変化し,制約の線形化への最適化がILPやPBの解法にとって不可欠であることが示唆された。
関連論文リスト
- Disciplined Bilevel Programming [9.272977870242562]
双レベル最適化は階層的決定問題に対する自然なモデリング言語を提供する。
既存の数値解法の適用は通常、実質的な手作業の分析と修正が必要である。
そこで我々は,楽観的な二段階問題の特定と解決を可能にするシンボリックフレームワークDBLPを紹介した。
論文 参考訳（メタデータ） (2026-09-01T03:22:48Z) - Complementarity by Construction: A Lie-Group Approach to Solving Quadratic Programs with Linear Complementarity Constraints [9.967127506836453]
ロボット工学における多くの問題は、連続力学と離散事象の混合に対する推論を必要とする。
JuliaでC++で実装したオープンソースのソルバであるMarbleを提供しています。
論文 参考訳（メタデータ） (2026-04-13T19:31:41Z) - GPU Accelerated Compact-Table Propagation [1.7249361224827533]
この研究は、変数の値の条件を代替オプションの列挙として指定するために使われる、テーブル制約と呼ばれる特定の形式の制約に焦点を当てる。
有限領域変数の集合上のすべての条件は最終的に有限ケースの集合として表現できるので、テーブルは他の制約をシミュレートすることができる。
本稿では,テーブルの最先端の伝搬アルゴリズムであるCT(Compact-Table)アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2025-07-24T13:53:49Z) - Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。
ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。
XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
論文 参考訳（メタデータ） (2025-06-03T17:46:53Z) - A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions [0.0]
線形ノルムバウンド制約の問題は、ポートフォリオ最適化、機械学習、機能選択など、さまざまなアプリケーションで発生する。
本稿では,これらの問題をグローバルに解決するための新しいグラフベース手法を提案する。
論文 参考訳（メタデータ） (2025-05-06T18:09:54Z) - Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。
思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。
SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
論文 参考訳（メタデータ） (2025-04-13T13:35:41Z) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳（メタデータ） (2023-10-27T23:24:37Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。