制約論理プログラミング
算術領域(Arithmetic Domain)は、整数領域、有理数領域、実数領域などがある。扱える制約は代数式で表される代数制約で、大きく以下の2種類に分かれる。
線型制約 :線型代数方程式/不等式
非線型制約:非線型代数方程式/不等式
線型制約はシンプレックス法などにより効率的に解け、多くの制約論理プログラミング言語でサポートされている。非線型制約は一般的な解法が無いため、遅延評価により非線型の式が線型になった後(例えば、 X*Y+Y*Y=-3 & Y=2 → 2*X+4=-3 )に評価したり、代数方程式をより扱いやすくするためブッフバーガーアルゴリズムで求めたグレブナー基底(Gröbner basis)で正規化した式で評価するなどの方法がとられる。 以下は実数領域での非線型制約を扱う制約論理プログラミング言語CLP(R)のプログラム例である。
以下はプログラムの実行例で、具体的な値が求まればその値が、そうでなければ各値の方程式が結果として返る。
制約が矛盾しなかった場合は解と"Yes"を、矛盾すれば"No"を結果として返すが、非線型のままの制約が残ってしまいYes/Noとも判定できない場合もあり、その場合は残った制約の式と"maybe"を結果として返すようになっている。