制約プログラミング

制約プログラミング（CP）^[1]は、人工知能、コンピュータサイエンス、オペレーションズリサーチの幅広い技術を活用した組み合わせ問題を解決するためのパラダイムです。制約プログラミングでは、ユーザーは一連の決定変数の実行可能なソリューションに対する制約を宣言的に記述します。制約は、実行するステップやステップのシーケンスを指定するのではなく、見つけるべきソリューションの特性を指定するという点で、命令型プログラミング言語の一般的なプリミティブと異なります。制約に加えて、ユーザーはこれらの制約を解決するための方法も指定する必要があります。これは通常、時系列バックトラッキングや制約伝播などの標準的な方法を利用しますが、問題固有の分岐ヒューリスティックなどのカスタマイズされたコードを使用することもできます。

制約プログラミングは、制約を論理プログラムに埋め込む制約論理プログラミングに由来し、その形で表現されます。この論理プログラミングの派生は、JaffarとLassez ^{[2]によるもので、彼らは1987年に}Prolog IIで導入された特定の制約クラスを拡張しました。制約論理プログラミングの最初の実装は、Prolog III、CLP(R)、およびCHIPでした。

制約は、論理プログラミングの代わりに、関数型プログラミング、項書き換え、命令型言語と組み合わせることができます。制約を組み込んだプログラミング言語には、Oz（関数型プログラミング）やKaleidoscope （命令型プログラミング）などがあります。多くの場合、制約は命令型言語では制約解決ツールキットを介して実装されます。これは、既存の命令型言語用の独立したライブラリです。

制約論理プログラミング

制約プログラミングとは、ホスト言語に制約を埋め込むことです。最初に使用されたホスト言語は論理プログラミング言語であったため、この分野は当初「制約論理プログラミング」と呼ばれていました。この2つのパラダイムは、論理変数やバックトラッキングなど、多くの重要な機能を共有しています。今日では、ほとんどのProlog実装には、制約論理プログラミング用のライブラリが1つ以上含まれています。

両者の違いは、主にそのスタイルと世界をモデル化するアプローチにあります。問題によっては、論理プログラムとして記述する方が自然（つまり単純）である一方、制約プログラムとして記述する方が自然なものもあります。

制約プログラミングのアプローチは、多数の制約が同時に満たされる世界の状態を探索することです。問題は通常、多数の未知の変数を含む世界の状態として表現されます。制約プログラムは、すべての変数の値を探します。

時間的同時制約プログラミング (TCC) と非決定性時間的同時制約プログラミング (MJV) は、時間を処理できる制約プログラミングのバリエーションです。

制約充足問題

制約とは、複数の変数が同時に取ることができる値を制限する、複数の変数間の関係です。

定義—有限領域上の制約充足問題 (または CSP) は、次の 3 つの条件で定義されます。 $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$

${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ 問題の変数の集合です。
${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ は変数のドメインの集合、すなわち、である。 $k\in [1;n]$ $x_{k}\in {\mathcal {D}}_{k}$
${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ は制約の集合です。制約は、変数の集合と、それらの変数に同時に許容される値の集合を定義する関係によって定義されます。 $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ ${\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ ${\mathcal {X}}_{i}$

制約には 3 つのカテゴリがあります。

外延的制約: 制約は、それを満たす値の集合を列挙することによって定義されます。
算術制約: 制約は算術式によって定義されます。つまり、を使用します。 $<,>,\leq ,\geq ,=,\neq ,...$
論理制約: 制約は明示的なセマンティクス (つまり、AllDifferent、AtMostなど)を使用して定義されます。

定義— CSP の割り当て (またはモデル)は、次の組み合わせによって定義されます。 ${\mathcal {A}}$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$

${\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}$ 変数のサブセットです。
${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\数学 {A}}_{k}}\}$ 割り当てられた変数が取る値のタプルです。

代入とは、変数をその定義域の値に関連付けることです。部分代入とは、問題の変数の一部に代入することです。全代入とは、問題の変数すべてに代入することです。

特性- CSP の割り当て（部分的または全体的）と、などの制約が与えられた場合、制約の変数のすべての値がに属する場合にのみ、割り当ては制約を満たします。 ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ $P$ ${\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}$ ${\mathcal {A}}$ $C_{i}$ ${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ }}x_{i}\in {\mathcal {X}}_{i}\}} となる$ $C_{i}$ ${\mathcal {R}}_{i}$

定義— CSP のソリューションは、問題のすべての制約を満たす全体的な割り当てです。

CSP のソリューションを検索する際に、ユーザーは次のことを希望できます。

解決策を見つける（すべての制約を満たす）
問題のすべての解決策を見つけること。
問題の不満足性を証明する。

制約最適化問題

制約最適化問題 (COP) は、目的関数に関連付けられた制約満足問題です。

最小化（最大化）COP の最適解は、目的関数の値を最小化（最大化）する解です。

COP のソリューションを検索中に、ユーザーは次のことを希望できます。

解決策を見つける（すべての制約を満たす）

目的に関して最善の解決策を見つけること。
発見された最良の解決策の最適性を証明すること。
問題の不満足性を証明する。

摂動モデルと改良モデル

制約ベースプログラミング言語は、2つのアプローチのいずれかに従います。^[3]

改良モデル：問題内の変数は最初は未割り当てであり、各変数はその範囲または定義域に含まれる任意の値を持つことができると仮定されます。計算が進むにつれて、ある変数の定義域内の値が他の変数の可能な値と矛盾することが判明した場合、各変数に単一の値が見つかるまで、その値は切り捨てられます。
摂動モデル：問題内の変数には単一の初期値が割り当てられます。異なるタイミングで、1つまたは複数の変数に摂動（古い値の変化）が生じ、システムはその変化を伝播させ、他の変数に摂動と一致する新しい値を割り当てようとします。

制約充足問題における制約伝播は改良モデルの典型的な例であり、スプレッドシートにおける数式評価は摂動モデルの典型的な例です。

洗練モデルは変数が単一の値を持つことを制限しないため、より汎用性が高く、同じ問題に対して複数の解を導くことができます。しかし、混合命令型制約のオブジェクト指向言語を使用するプログラマーにとっては、摂動モデルの方が直感的です。^[4]

ドメイン

制約プログラミングで使用される制約は、通常、特定の領域に限定されます。制約プログラミングでよく使用される領域には、以下のようなものがあります。

真偽制約のみが適用されるブール領域（ SAT問題）
整数領域、有理数領域
間隔領域、特にスケジューリング問題^[5]
線形領域では線形関数のみが記述され、分析されます（ただし、非線形問題へのアプローチも存在します）
有限領域、制約は有限集合上で定義される
上記の2つ以上の混合ドメイン

有限領域は、制約プログラミングの最も成功した領域の一つです。一部の分野（オペレーションズ・リサーチなど）では、制約プログラミングは有限領域における制約プログラミングと同一視されることがよくあります。

制約伝播

局所整合性条件は、制約充足問題における変数または制約のサブセットの整合性に関連する特性です。これらは探索空間を縮小し、問題の解決を容易にするために利用できます。ノード整合性、アーク整合性、パス整合性など、様々な種類の局所整合性条件が活用されます。

あらゆる局所整合性条件は、問題の解を変えずに問題自体を変える変換によって強制することができます。このような変換は制約伝播と呼ばれます。^[6]制約伝播は、変数のドメインを縮小したり、制約を強化したり、新しい制約を作成したりすることで機能します。これにより探索空間が縮小され、一部のアルゴリズムによって問題が解きやすくなります。制約伝播は、一般には不完全ですが、特定の場合には完全な充足不可能性チェッカーとしても使用できます。

制約解決

制約充足問題を解決するための主なアルゴリズム手法には、バックトラッキング探索、局所探索、動的計画法の3つがあります。^[1]

バックトラッキング検索

バックトラッキング検索は、いくつかの計算問題、特に制約充足問題に対するすべての（または一部の）解決策を見つけるための一般的なアルゴリズムであり、解決策の候補を段階的に構築し、候補が有効な解決策に完了する可能性がないと判断するとすぐに候補を放棄（「バックトラック」）します。

ローカル検索

局所探索は、問題の解を見つけるための不完全な手法です。これは、すべての制約が満たされるまで変数の割り当てを反復的に改善していくことに基づいています。特に、局所探索アルゴリズムは通常、割り当ての各ステップで変数の値を変更します。新しい割り当ては、割り当て空間において以前の割り当てに近いため、局所探索と呼ばれます。

動的計画法

動的計画法は、数学的最適化手法であると同時に、コンピュータプログラミング手法でもあります。複雑な問題を再帰的に分割することで、問題を単純化することを指します。一部の意思決定問題はこの方法では分解できませんが、複数の時点にまたがる意思決定は、多くの場合再帰的に分割されます。同様に、コンピュータサイエンスでは、問題を部分問題に分割し、それらの部分問題の最適解を再帰的に見つけることで最適に解決できる場合、その問題は最適な部分構造を持っていると言われます。

例

有限領域における制約を表現する構文はホスト言語によって異なります。以下は、制約論理プログラミングにおける古典的なアルファベットパズル「SEND+MORE=MONEY」を解くPrologプログラムです。

% このコードは、環境提供の
CLPFD 制約ソルバーライブラリを使用することで、YAP と SWI-Prolog の両方で動作します。他の Prolog 環境や他の制約ソルバーを使用するには、若干の修正が必要になる場合があります
。
:-  use_module ( library ( clpfd )). 
sendmore ( Digits )  :- 
   Digits  =  [ S , E , N , D , M , O , R , Y ],    % 変数
   Digits  ins  0..9を作成、                % 変数にドメインを関連付けます
   S  #\=  0 、 % 制約: S                        は0 と異なる必要があります
   M  #\=  0 、
   all_different ( Digits )、          %すべての要素は異なる値を取る必要があり
                ます1000 * S + 100 * E  +  10 * N  +  D %その他 の 制約     + 1000 * 
              M +  1000 * O + 100 * N + 10 * E + Y 、label ( Digits ) 。%検索を開始します

インタープリタはパズルの各文字に対して変数を作成します。演算子はinsこれらの変数のドメインを指定するために使用され、変数は{0,1,2,3, ..., 9}の値の集合に収まるようにします。制約S#\=0とは、M#\=0これら2つの変数が0を取らないことを意味します。インタープリタがこれらの制約を評価する際、2つの変数のドメインから0を削除することで、ドメインを縮小します。次に、制約がall_different(Digits)検討されます。制約はドメインを縮小しないため、そのまま保存されます。最後の制約は、文字に割り当てられる数字は、各文字を対応する数字に置き換えたときに「SEND+MORE=MONEY」が成立するように指定されます。この制約から、ソルバーはM=1と推論します。変数Mを含む保存済みのすべての制約が有効化されます。この場合、制約の制約伝播all_differentにより、残りのすべての変数のドメインから値1が削除されます。制約伝播は、すべての定義域を単一の値に縮約することで問題を解決する場合もあれば、定義域を空集合に縮約することで問題に解が存在しないことを証明する場合もありますが、充足可能性や充足不可能性を証明することなく終了する場合もあります。ラベルリテラルは、実際に解の探索を行うために使用されます。

参照

参考文献

^ ab Rossi, Francesca ; Beek, Peter van; Walsh, Toby (2006). 制約プログラミングハンドブック. Elsevier. ISBN 978-0-08-046380-3。
^ Jaffar, Joxan; Lassez, JL. (1987). 「制約論理プログラミング」 . POPL87: 第14回ACM SIGPLAN-SIGACTプログラミング言語原理シンポジウム. Association for Computing Machinery. pp. 111– 9. doi :10.1145/41625.41635. ISBN 978-0-89791-215-0。
^ Borning, A.; Freeman-Benson, B.; Wilson, M. (1993). 「制約階層」 . Mayoh, B.; Tyugu, E.; Penjam, J. (編).制約プログラミング. NATO ASI F. Vol. 131. Springer. p. 76. doi :10.1007/978-3-642-85983-0_4. ISBN 978-3-642-85983-0。
^ Lopez, G.; Freeman-Benson, B.; Borning, A. (1993). 「Kaleidoscope: 制約命令型プログラミング言語」(PDF) . Mayoh, B.; Tyugu, E.; Penjam, J. (編).制約プログラミング. NATO ASI F. Vol. 131. Springer. pp. 313– 329. doi :10.1007/978-3-642-85983-0_12. ISBN 978-3-642-85983-0。
^ バティスト、フィリップ、パペ、クロード・ル、ヌイテン、ウィム (2012). 制約ベース・スケジューリング：制約プログラミングのスケジューリング問題への適用. シュプリンガー. ISBN 978-1-4615-1479-4。
^ Bessiere, Christian (2006). 「制約伝播」.制約プログラミングハンドブック. 人工知能の基礎. 第2巻. Elsevier. pp. 29– 83. CiteSeerX 10.1.1.398.4070 . doi :10.1016/s1574-6526(06)80007-6. ISBN 9780444527264。

外部リンク

ウィキメディアコモンズには、制約プログラミングに関連するメディアがあります。

制約プログラミングの原理と実践に関する国際会議。制約プログラミング協会。
Barták, Roman (1998). 「制約プログラミングのオンラインガイド」. プラハ・カレル大学.
archive.todayの Mozart プログラミングシステム(2012 年 12 月 5 日アーカイブ)、Ozベースのフリーソフトウェア ( X Window Systemスタイル)
Cork Constraint Computation Centre at archive.today (2013年1月7日アーカイブ)
Shirriff, Ken (2025年10月). 「制約ソルバーを用いたNYTimes Pipsパズルの解法」
スカセラティ、ブライアン (2019). 「制約充足問題」(PDF) . CPSC 470 – 人工知能. イェール大学.