9/17 からのカンファレンス本編についても簡単にレポートしたいと思います。 使用されたプレゼンテーション資料の一部は、CP2013 のスケジュールのWebページから参照することができるようです。
レクチャーの内容は理論的なもの、応用に関するものなど多岐にわたりますが、 ここでは NDiS でも参加している MiniZinc Chalenge の結果発表についてと、 応用事例からいくつかピックアップして紹介したいと思います。
MiniZinc Challenge 結果発表
結果については https://www.minizinc.org/challenge2013/results2013.html から参照することができます。
昨年度まで全てのカテゴリーで金メダルだった Gecode が Fixed Search 以外ではメダルなし、 Opturion/CPX と OR-Tools が大躍進と、波乱の結果となりました。 (この結果はプレゼンテーションでは “King is dead.” と表現されていました)
OR-Tools は昨年度もエントリーしていたのですが、 「必要なところからインプリメント(ワークショップでのプレゼンから)」した結果が反映されたのでしょう。 Opturion/CPX はいわば主催者の自信作と言ってもよいもので、貫禄勝ちといったところでしょうか。
そんな中、Free Search 部門では NTTデータセキスイシステムズから参加している izplus が 3位に踏みとどまったのは健闘した方だと思います。Parallel Search 部門の結果と見比べると、 マルチコアへの対応具合も今後は重要になってくるのかもしれません。
izplus がどのようなソルバであるかは「izplusとは (2013)」で解説しています。
Application Track
制約プログラミングというと、パズルやスケジューリングの文脈で語られることが多いと思いますが、 実際の応用例の発表をみるとまた違った視点が得られるかもしれません。 という訳で、発表の中から私見で興味深かったものについていくつか紹介したいと思います。
プレゼン資料の多くは CP2013 のスケジュールのページから見られるようになっているようです。
Solving the Agricultural Land Allocation Problem by Constraint-Based Local Search
(Quoc Trung Bui, Quang Dung Pham, Yves Deville)
ベトナムでの農地の集約と再分配を CP を用いた行ったという事例の発表です。農家が小さな農地をバラバラに所有している状態を一旦整理し、大きな農地として公平に割り当てなおすことで、農業の効率を上げようという活動が行われているそうです。
農地の性質、家からの距離、水路などさまざま条件を考慮し、従来は人が考えていた割り当てに比べて非常に満足できる結果が得られたということです。
Constraint-based Approaches for Balancing Bike Sharing Systems
(Luca Di Gaspero, Andrea Rendl, Tommaso Urli)
貸自転車を需要に応じてステーション(Bike station)に再分配するという事例の発表です。シェアされている自転車がステーション間でアンバランスになると、車でまとめて運んで再分配するシステムの計画だとのことで、自転車の利用が発達している国らしいと思われる内容でした。
LNS(Large Neighbourhood Search)を使用したとのことでしたが、LNSは他の発表でもいくつか目にしたので、流行中なのかもしれません。
Automatic Generation and Delivery of Multiple Choice Math Quizzes
(Ana Paula Tomás, José Paulo Leal)
数学の補習用の教材を自動で作成するという事例の発表です。文法と制約に従って問題用の数式と選択肢を作り、LaＴeXの形式で出力するのだそうです。
生徒の犯しがちな誤りを文法に入れてそれらしい誤りの選択肢を作るというのは面白いと感じました。
Constrained Wine Blending
(Philippe Vismara, Remi Coletta, Gilles Trombettoni)
ワインの香りを構成する化学物質について着目し、いろいろな比率でそれを含むワインをブレンドして目標とするワインを作る、という事例の発表です。
人の感性が物をいいそうな領域ですが、こんなところにも最適化問題があるのか、というちょっとした驚きがありました。