制約プログラミングは、
「問題を制約の集合として記述してコンピュータに与えると、コンピュータが制約を充たした答を見つけてくれる」
ことを目指すプログラミング・パラダイムのことだと言えます。
重要な点は、制約による問題の記述とその問題を解く手順・方法とを区別することです。制約による問題の記述は「宣言的」な性質を持ちます。制約の重要な特徴と して、「処理の方向が固定されない」点が挙げられますが、これは「宣言性」という性質を徹底化したものと考えることができます。
一方、問題解決の方法は、さまざまな方法がありえるでしょうが、狭義での制約プログラミングでは、問題に存在する制約を上手に利用して効率よく答を見つける技法が研究の対象となっているようです。制約を充たす解を求めるプログラムのことを制約解消系、制約ソルバーと呼びます。
実際の制約解消のアルゴリズムは、制約の種類（どのような変数に対するどのような制約か）に依存して異なります。
何が制約プログラミングではないのか? - 関連分野
上記のような定義では、「どのように解くか」について、具体的なアルゴリズムが指定されているわけではありませんから、広義にとれば非常に多くの領域が含まれます。制約充足問題（CSP）に対する解法としては、思い付くままに挙げても、
- OR（オペレーションズリサーチ）で研究されてきた様々なアルゴリズム、線形計画法、ニュートン法、動的計画法、etc.
- 木探索ベースの様々な手法
- 併合法やプログラミング変換における簡約などのような制約の書換えに基づく手法<
- minimum-conflict、タブー探索、シミュレーテッドアニーリング（SA)などの解改善アルゴリズム
- ニューラルネットワークを用いた探索
- 遺伝的アルゴリズム（GA)
など、数多くの手法が考えられます。また、広義での制約パラダイムということであれば、
- SCMなどにより注目を集めているTOC理論（Theory of Constraint）
- 自然言語処理における制約に基づく文法理論(HPSG, Constraint Grammer, etc.)
などを思い浮かべることもできるでしょう。
何が制約プログラミングか、何がそうでないかについては、色々な立場があると思われますし、厳密な定義を行うことに意味があるとは思えません。
けれども、制約プログラミングのカバーする領域の「中心」にあたる部分については、概ね、以下のように言えるのではないでしょうか?
- 制約は数値的なものに限定しない。問題の計算領域を問わずに制約として扱う。
- 問題空間の中に含まれる矛盾を検出し、整合性を維持するための効率的なアルゴリズムが中心技術となる。
- 解の探索法としては木探索法がベースで、探索の際に制約を積極的に利用して探索空間の縮小を行うことが基本となる。
問題の計算領域を問わずに制約として扱う、というパラダイム的な側面は特に重要だと思われます。
もちろん具体的にはそのうちの特定領域のみに絞った研究や、応用がなされますし、ある領域については関連領域で優れた手法が提案されている場合には、そうした手法を取り込む枠組みとして、制約に基づくパラダイムを考えることができるからです。
その意味で、広義での制約プログラミングは、これまで様々な分野で研究されてきた手法を関連付ける結節点のような役割を果たしているといえると思います。
従って、本サイトでは、狭義の制約プログラミングのみではなく、可能な限り、広義の制約充足問題（CSP）のパラダイム、制約パラダイムについても扱っていく方針です。
制約論理プログラミングという言葉を聞いたことはあるけど…
制約論理プログラミング(Constraint Logic Programming)というのは、上述のような制約プログラミングを論理プログラミングの拡張として実現したものです。論理プログラミングは、制約プログラミングと多くの特徴を共有しており、制約プログラミングの一部であると言ってもよいほどです。実際、論理プログラミング言語の代表とされているPrologの処理系の多くは、現在、制約ソルバーを備えていますし、必ずしもPrologをベースとしていなくても、多くの制約プログラミングのためのシステムは、論理プログラミングの考え方に基づいています。狭い意味での制約プログラミングは、制約論理プログラミングと同じものと言ってもよいと思います。
どのような特徴があるの?
制約プログラミングには、以下のような特徴があると言えるでしょう。
- 宣言的であり、情報の流れを一方向に固定しない。
- 制約される対象領域によって、制約解消の定義も解法も異なる。
- 制約を利用することにより探索の効率化が期待できる。
- プロトタイピングが容易。開発生産性が高い。
- オブジェクト指向パラダイムとの親和性が高い。
宣言性は、制約プログラミングの最も大きな特徴です。これは問題の定義と解法を分離することに関係します。関数プログラミングも、論理プログラミングも宣言性という特徴は持っていますが、関数プログラミングにおいては、情報の流れは決まっています。また、論理プログラミング言語も実装上は情報の流れが決まっていることがありました。勿論、情報の流れが固定できることは、多くの場合、問題解決の効率を考えると有利です。また、いつも双方向性が可能であるとは限りません。しかしながら、宣言性という点では、制約プログラミングは最も徹底的であると言えるでしょう。
更に、制約を利用することにより探索の効率化を図るという点で、問題解決の効率にも配慮しているといえます。ただし、制約される対象領域によって制約解消の定義も解法も異なるため、制約ソルバーは対象領域毎に用意する必要があります。逆に見れば、いろいろな効率のよい解法を、制約プログラミングの枠組みの中に集めることができるため、非常に柔軟でオープンであるとも考えられます。
プロトタイピングが容易であるとか、開発生産性が高いという特徴は、その多くを宣言性に負っているといえます。また、制約をオブジェクト間の関係と考えれば、オブジェクト指向パラダイムとの親和性が高いことは予想されますが、実際、多くの制約処理系はオブジェクト指向になっています。
実用になるの?
制約プログラミングは、様々な実用的なシステムを開発するための基礎技術の一つであり、様々な分野への適用が可能です。1990年代初頭に商用のシステムが販売されはじめて以来、数多くの実用システムが制約プログラミングに基づいて開発され、運用されてきました。
どのような分野に適用されてきたかについては
どういう点が優れているの?
特徴として述べた項目と重複しますが、制約プログラミングの長所としてあげられるのは以下のような点です。
- 宣言的なので、特定の解き方を前提とせずに、解くべき問題の記述に専念できます。
- 様々な解き方を場合場合によって使い分けるようなシステムを構成する際の枠組みとなることができます。
欠点は?
一方、制約プログラミングの欠点として挙げられるのは以下のような点です。
- 宣言的であるということは、プログラムを見ただけでは挙動がわからないことでもあります。手続き型言語のように、書いた通りに動く、というわけには行きません。また、宣言的な書き方がいつでも書きやすいわけではありません。
- 大域的な探索を行うアプローチでは、制約解消による探索の効率化があっても、なお解を求めるための時間的・空間的コストが大きすぎる場合があります。
なぜ流行らないの?
すでに述べたように、制約プログラミングには長所も短所もあり、必ずしも良いことづくめではありませんが、それにしても、制約プログラミングが流行しないのはなぜなのでしょう？これについては、以下のように考えられます。
- ハードウェアをはじめとする環境が、制約プログラミングを行うには貧弱すぎ、制約プログラミングは「高価な技術」だった。
- 論理プログラミングの拡張という側面が強調されすぎて、論理型言語と不可分のものと考えられる傾向にあった。
実際、制約プログラミングが実用化された初期の時代には、制約プログラミングは最先端の技術であるという側面を強調した宣伝がされていたように思われますし、それに応じて商用のツールも非常に高価なもので、利用できるのは大規模なプロジェクトにかぎられていました。
しかし、今や時代が変わり、以下のような状況になっています。
- ハードウェアの能力は飛躍的に向上し、当初は高価なワークステーション上でした利用できなかった制約プログラミングが、性能では当時のワークステーションを遥かに上回り、しかも安価なPC上で利用できるようになった。
- 制約プログラミングは確かに論理プログラミングの拡張と考えることができますが、論理プログラミングの特定の実装を前提に考える必要はありません。実際、これまでも論理型言語の拡張ではない、手続き型言語（特にオブジェクト志向型言語）上のライブラリとして制約処理系が実装され、その上で多くの実用アプリケーションを構築することが可能であることが実証されてきました。
まだ、制約プログラミング技術は若く、条件が整ってきたこれからが本格的な実用の時代といえるのではないでしょうか？