制約プログラミングに関する国際カンファレンス CP2013 (The 19th International Conference on Principles and Practice of Constraint Programming) に参加する機会がありましたので、感想などを紹介したいと思います。
CP2003 はスウェーデンのウプサラという都市で 2013/9/16～2013/9/20 に開催されました。 会場となったウプサラ大学は 1477年に創設された北欧最古の大学だということで、 写真のような立派な建物が使用されました。
9/16 はワークショップ、9/17～9/20 が各発表者が講演を行うメインの カンファレンスということになっており、NTTデータセキスイシステムズでは 9/16 に行われたワークショップの一つ、“CP Solvers: Modeling, Applications, Integration, and Standardization” で iZ-C の紹介を行いました。
また 9/17 に結果発表の行われた MiniZinc Challenge 2013 にも iZ-C を使用したソルバ izplus で参加しています。
ワークショップ (CP Solvers)
CP Solvers: Modeling, Applications, Integration, and Standardization は、 CP ソルバとその産業界での応用についての概要を俯瞰し、よりいろいろなところで使われていくようにするにはどうしたらよいのか、 という目的の元に開催されたワークショップとなります。
また、ワークショップの開催に先だって、ソルバのベンダーへの呼びかけが行われ、 CPソルバのカタログ “Catalogue of Constraint Programming Tools” が整備されました。
各発表について、私見ですが簡単にまとめてみたいと思います。
（各発表の概要とプレゼンテーションは http://cp2013.a4cp.org/node/99 から見ることができましたが、 2020年現在、CP2013 のウェブサイトは残念ながら残っていません。 web.archive.org にアーカイブされたものは https://web.archive.org/web/20161025182003/http://cp2013.a4cp.org/node/99 で参照できるようです)
CP Solvers/Learning Constraint Programming
制約プログラミングについて詳細な blog を書いていらっしゃる Håkan Kjellerstrand さんの発表です。(blog はこちら http://www.hakank.org/constraint_programming_blog/)
いろいろなソルバを調査した結果のまとめや、関連ブログの紹介などさまざまな役に立つ情報の紹介がありましたので、気になる方はプレゼンテーション資料をチェックしてみてください。
ソルバの選び方として、
ホスト言語が決まっているか 使いたい制約が存在するか 初心者なら高レベルの言語を選択するのがよい などのまとめはなるほどと思いました。
また、CP を広めるための情報発信(ブログなど)の重要性を説かれていました。
Gecode – an open constraint solving library.
制約プログラミング関係の研究、応用では比較的広く使われている Gecode の紹介です。 (Webページはこちら http://www.gecode.org/)
研究者の方が長い時間をかけて作られたもので、売りは以下のようなものだそうです。
- 100% 近いカバー率のテスト (16% がテストコードとのこと)
- API とドキュメントの豊富さ
- オープンソース (MIT license)
- いろいろな標準言語への準拠 (MiniZinc, AMPLなど)
キャッチフレーズとして、“You can do is we can do.”. “You can know is we can know.” を挙げられていました。 168 kloc、71 kdoc ということで、ドキュメントの豊富さがうかがえます。
Choco3: an Open Source Java Constraint Programming Library.
Java で書かれた制約ソルバで、同時に発表が行われた JaCoP とならんでかなりメジャーなライブラリではないかと思います。 (Webページはこちら http://www.emn.fr/z-info/choco-solver/)
1999年ごろから開発が開始され、2003年にChoco 1.0 がリリース(BSD License)されたということで、かなり長い歴史をもつものです。
ソルバに規模は以下のようなものです。60k以上のコード、700のクラス
また実用例としてデータセンターのレイアウト問題 (100,000VM という巨大なもの)が紹介されていました。
JaCoP - Java Constraint Programming Solver.
こちらも Java で記述された制約処理系です。(Webページはこちら http://jacop.osolpro.com/) 2001年から開発が開始され、2003年に最初のリリースがされました。規模としては 100,000行で、 集合(set)に関する制約が充実していて効率がよいというのが強みだとのことです。
JavaVM 上で動く他の言語でのモデル記述も紹介されましたが、Scala での記述は簡潔で分かりやすいと感じました。
実用例として、命令語を制約ベースで選択する問題が紹介されていました(Instruction selection and scheduling)。 事後に調べましたが、この問題は以下の論文(PDF)かもしれません。
- Constraint-Driven Instructions Selection and Application Scheduling in the DURASE system https://hal.inria.fr/file/index/docid/449747/filename/charot_asap09.pdf
Model Presolve, Warmstart and Conflict Refining in CP Optimizer.
特定のソルバではなく、CPソルバに適用可能な手法の発表でした。とはいえ、 IBM ですから CPLEX 関連の技術ではないかと思います。 (CPLEX の Webページはこちら http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/)
以下の手法が紹介されていました。
-
Presolve — 部分式が共通だったら共通の変数で置き換えるとか、違う変数として定義されていても同じ意味だったら共通の変数にするとか、 そういったものです。Unification だよね? という声も。
-
Warmstart — リスタートの時に前回の情報を利用する手法だと思います。
-
ConflictRefiner — 問題が解けないときに、どの制約のせいなのかを見つけ出す手法です。OPL というモデル定義言語を利用して、 このファイルの何行目のこの制約です、と指摘できるという例が紹介されていました。
Xpress-Kalis: A CP solver integrated in the FICO Xpress Optimization Suite.
FICO社の Xpressions への CP 拡張で、これ自体はソルバではなく CPソルバへのインターフェースを提供するものだそうです。 (これ自体の開発は Artelys社。 Webページはこちら http://www.artelys.com/en/optimization-tools/artelys-kalis/xpress-kalis)
モデリング言語には Mosel というものを使用し、スケジューリング特化した制約が記述できるそうです。
また、Xpress の機能 (Xpress IVE) を利用してスケジュールの結果がガントチャートなどで表示できるとのことでした。
実用例として、原発のメンテナンス時期を決める複雑な問題が紹介されていました。
OR-Tools solver.
Google で開発されているソルバです。(Webページはこちら http://code.google.com/p/or-tools/)
他のソルバは機能の充実をアピールしていたのに対して、まだまだ足りないけれども必要な機能から実装している、という Googleらしさが特徴だと思いました。
他言語のバインドもいくつか紹介紹介あれていましたが、C# の LINQ を使った記述が面白いと思いました。集合から制約を満たすものを選択するといった用途には LINQ が向いているかもしれません。
また、local search との組み合わせの使用例が多い、というレポートが印象的でした。
JSR331 Standard: Current State and Future Plans.
Java の制約プログラミング API の標準についての話です。
これにより、ビジネスアプリケーションを記述するレイヤとソルバを記述するレイヤがきれいに分けられるというもので、いかにも Javaらしいと思いました。
jsr331.org というサイトで情報を入手できます。
また、発表者の Jacob Feldman さんが関連する blog を書いています。(http://cpstandard.wordpress.com/)
The modeling system AIMMS for developing Mathematical Programming and Constraint Programming applications.
AIMMS 自体は最適化のための汎用のシステムで、CPについてはソルバのためのインタフェースを持っているというタイプのものです。 (Webページはこちら http://business.aimms.com/)
発表の方は、技術をどうやって現実のアプリケーションにつなげていくか、といった切り口になるもので、 ワークショップの課題に応えようとするまじめなプレゼンテーションが印象的でした。
iZ-C: A Constraint Programming Library.
NTTデータセキスイシステムズで開発した制約プログラミング用のライブラリについての紹介です。 (Webページはこちら。http://products.ndis.jp/iz/)
Webページで紹介している事例に加え、MiniZinc Challenge 参加のためのソルバ izplus の紹介なども行いました。 制約プログラミングを使用した製品「快決！シフト君」は、 この手の技術を使ったソフトウェアとしては珍しい売上本数ということで関心を集めたようです。
Constraint Programming in AMPL.
AMPL はメジャーなモデリング言語の一つです。(Webページはこちら http://www.ampl.com/)
CPソルバへのインターフェースも持っているので、いろいろな CPソルバを切り替えて使えます、ということです。
また、以前はアプリから呼び出すにはファイルを経由するなどする必要がありましたが、現在は Java, C# などの API も持っているのでもっと密に結合したアプリケーションも開発可能とのことです。
Numberjack.
Python 上に構築された、制約プログラミングのためのフレームワークで、Python でモデリングを行い、バックエンドのソルバで問題を解く、というタイプのものです。(Webページはこちら http://numberjack.ucc.ie/)
“Prototyping is useful!” のスライドの絵はなかなか印象的で、使い慣れた言語でモデリングを簡単にモデリングを行えることの重要性が印象づけられました。
ロゴも面白いですね。
パネルディスカッション
各発表者の発表後、パネルディスカッションが行われました。司会のSimonisさんの「何でこんなにたくさんのソルバがあるのか?」という質問を皮切りにいろいろな議論がなされました。
これに関連しては、ソルバごとに得意不得意がある、ソルバそれ自体とソルバへのインタフェースをもつモデル言語が存在する、アカデミックでは論文が書けることが重要だが商用ではきちんとテストした上でサポートまで行う必要がある、ライセンスフィーの違いがある、などの話が出されました。
また、CPがなぜ広まらないのか、広まるにはどうしたらよいか、という話については、MIP, LPの専門家が比較的多い(コンピュータサイエンスの大学のコースの問題ではという指摘もあり)、簡単な問題だと MIP でも LP でも CP でも解けてしまう、CP のイベントで話しているだけでは駄目で、もっと他で情報を発信しなければならない、などの意見が出されました。