last update: 26 October 2007

研究・応用の歴史

制約プログラミングの研究はおおむね1980年代から盛んになり、1990年代に実用の時代に 入り、現在も活発な研究・実用が重ねられています。
制約プログラミング研究は世界中で行われていますが、日本では、ICOT（現AITEC）に おける主要な研究テーマの一つであり、数多くの処理系が開発されるなど、多くの研究 成果を生み、制約プログラム研究の進展に大きく寄与したと言われています。
以下では簡単に、その経過を時系列で辿ってみます。

初期の研究(1980年くらいまで)

• SketchPad(Sutherland, 1963) -- 対話型のドローイングツール。最も初期の制約システム。
• 画像のラベリング(Waltz,1972) -- 後年、制約解消アルゴリズムとして再発見された。
• ThingLab(Boring, 1981) -- 対話型のドローイングツール。
• ALICE(1978) -- 汎用制約処理系の先駈け。

研究の活発化（1980年代）

主として論理プログラミングの拡張として盛んに研究されるようになり、汎用の制約処理系の開発が行われるようになりました。制約論理プログラミングと呼ばれることが多いのはそのためです。

• ICOT(日本）-- CAL, GDCC, CuPrologなど。現在AITECのソフトウェアアーカイブで公開されています。
• ECRC(ヨーロッパの共同研究機関) -- CHIP。Charme,CHIP V4などの商用の制約処理系のもとになりました。
• マルセイユ大（フランス）-- PrologIII。Prologの開発者によるものです。
• モナシュ大学（オーストラリア）、IBMワトソン研究所（アメリカ） -- CLP(R)。

実用化の時代（1990年代前半）

商用の制約処理系が開発・販売されました。
国内では、以下のようなシステムが販売されました。

• Charme(フランスBull社製、ISACが販売）-- Charmeは世界で初の商用の制約処理系です。ECRCのCHIPの成果を基にしています。
• CHIP V4(フランスCosytec社製、CRC総合研究所が販売）-- ECRCのCHIPを基本にして商用化したものです。
• ILOG Solver(フランスILOG社製）-- ILOG SolverはC++のライブラリで同社のLispのライブラリPECOSの後継です。
• IF Prolog(独IF Computer社・開発は独Siemens） -- 独Siemensの開発したSRI-Prologに基づいています。ECRCのCHIPの流れをくんでいます。

これらはみな汎用の開発環境であり、主として要員計画・生産スケジューリング・輸送計画などの計画問題、設計問題などのアプリケーション開発に用いられました。

CHIPとIF PrologはPrologの拡張と考えることができますが、Charmeは独自のシンタックスを持つ簡易言語のインタプリタとCのライブラリの2つの版が提供されていましたし、ILOG SolverはC++のクラスライブラリであり、全体としては制約論理プログラミングの枠組みにあるものの、手続き型言語での利用ができるようになり、他のシステムとの統合が容易になりました。

一方、研究も並列化などを中心に進み、論理プログラミングの枠を超えて他のパラダイムとの統合化の研究も盛んになりました。特にヨーロッパではESPRITプロジェクトの一環として、並列制約プログラミングの研究が行われ、多くの成果を挙げました。
この時期の研究成果としては、例えば以下のようなものがあげられます。

• Concurrent Constraint(Saraswat, 1994) -- 並列制約プログラミングの定式化を行ったものでその後の研究の出発点となりました。
• AKL(スウェーデンSICS) -- 並列論理プログラミングモデルであるAndorra Kernelモデルを出発点とし、並列制約論理プログラミング、関数型言語、オブジェクト指向などのパラダイムの統合の研究の先駆的な業績といわれています。
• Oz(ドイツDFKI) -- 独自のシンタックスを持つ言語で、この時期に開発が開始されました。その後SICS、ルーヴァンカトリック大学との共同開発になり、並列制約論理プログラミング、関数型言語、オブジェクト指向、分散プログラミングなどを統合するマルチパラダイムのプログラミング環境Mozartに発展して現在に至っています。

最近の動向

• コンピュータハードウェアの能力の向上は著しく、1990年代初頭に商用化が始まった 時点では高価なWS上で、メモリを増設していたものが、当時のWSの性能を遥かに 上回り、価格的には非常に安価なPC上が普及した結果、制約プログラミングは ようやく普通に使える技術になってきたと言えると思われます。
• 一時の商品化のラッシュの時期は過ぎましたが、その後も制約プログラミングに基づく実用的なアプリケーションの開発実績は地道に積み重ねられ、特に計画系システム構築の基本テクノロジーの一つに成長しました。
• 特に最近ではSCM(Supply Chain Management)が注目され、制約プログラミングの主要な適用分野である計画系システムが脚光を浴びるようなりました。特に複雑な制約条件を考慮したスケジューリングを行うスケジューリングシステムをAPSと呼んで従来のものと区別することがありますが、このAPSの実現手法の一つとして制約プログラミングが利用されています。
• また、ＴＯＣ理論や生物指向生産システムなど、広義での「制約」に注目する考え方・手法が最近、注目を集めています。
• 一方、JAVA言語の普及などと並行して、グラフィカルな側面に注目が集まっており、JAVA言語のライブラリ、JAVA言語の拡張を行った処理系も作成されています。
  
• Prologの処理系では制約ソルバを備えるシステムの数が増えています。
  
• また研究も、特に関数型言語との融合をはじめとする、マルチパラダイム化の研究のほか、探索における相転移のような研究も行われ、今後ますます、制約プログラミングの重要性は増していくものと思われます。