izplus とは MiniZinc Challenge に参加することを目的として iZ-C (NTTデータセキスイシステムズ社製の制約プログラミングライブラリ)を用いて作成された FlatZinc ソルバです。
通常、お客様向けの業務に iZ-C を適用する場合はその業務に合わせた解法を実装するのですが、 MiniZinc Challenge では様々な問題を解く必要があり、iZ-Cを活用して得られた知見を元に一般化した解法が用いられています。
このような理由により iZ-C に解法をプラスしたもの、という意味で「izplus」という名前が与えられています。
制約プログラミングでは制約伝搬による解空間の縮小が注目を浴びますが、 現在ではそれに加えてさまざまな高速化手法が提案されており、izplus でもそれらの手法が有効に機能することが確認されています。 以下では、簡単にそれらの手法を紹介したいと思います。
手法の紹介
リスタート
探索時に値を決定する変数の順序によって、問題を解くために必要な時間が大幅に変化することが知られています。 これは「悪い変数」を探索の初期に選ぶと、深さ優先探索(DFS)ではその変数の値は探索がかなり進むまで変更されないことが原因です。 例えば「Algorithms for Constraint Satisfaction Problems: A Survey (Vipin Kumar)」
リスタートは、「悪い変数」を選んでしまったと判断されるくらい探索の失敗が続いた場合はその探索は諦めて、変数選択順を変えて探索をやりなおす方法です。諦めるまでの期間が短すぎると探索が少なくなりすぎ、諦めるまでの期間が長すぎるとリスタートが十分に起こりません。この判断の仕方にはいくつかの方法があるようです。
例えば「On Universal Restart Strategies for Backtracking Search (Huayue Wu and Peter van Beek)」
SAT ソルバでは学習節の獲得と合わせて目覚ましい効果を上げているようですが、izplus では学習は行っていません。それでもかなりの効果があることが確認されています。
ローカルサーチ
制約プログラミングは制約充足問題に加えて、最適化問題に適用される場合があります。最適化問題は、 一旦「制約を全て満たした解」を求めてその時の目的変数が分かったら、「目的変数がさらに小さい」という制約が あるとみなして問題を解くことを繰り返すことで解くことができます。
この繰り返しの時に、それまでに得られた解の一部を使うことで余分な探索を省くことができるというのが ローカルサーチの基本的なアイデアです。
例えば「Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling (J. Christopher Beck)」
ローカルサーチでは探索の完全性を保証しないことが多いですが、izplusでは完全性を保証できるような手法を採用しています。 下記の疑似コード内の「ローカルサーチ」は「iZ-C: A Constraint Programming Library」(PowerPoint スライド)で説明されているものです。
while (true) {
/* restarting loop */
limit を小さい値にする;
while (true) {
ローカルサーチ(limit);
if (最適値が更新された) {
break;
}
if (探索空間を全て探索した) {
goto END;
}
limit を増加;
}
目的変数の値の制約を小さくする(最小化問題のとき);
}
END:
動的な変数選択順
先にも書きましたが、問題を解くにあたっては変数の選択順は非常に重要です。「first fail principle」はよく知られていますが、 実際に探索を行った時に失敗の原因となった変数を識別する手法もいくつか提案されています。
izplus でも候補となる値が少ない変数(smallest domain)を元にしつつ、少量のランダム要素を加味する、 探索中に失敗の原因となった変数を記録し失敗に応じて変数選択順を変更するといった手法を用いることで 効率のよい変数選択順を得ることに成功しています。
これからの課題
制約の学習
SATソルバでは学習節の獲得が探索の高速化に非常に有効であることが示されています。 制約プログラミングでも例えば「変数Aがa、変数Bがbの時は必ず失敗する」 のような学習が可能であることが示されており、その有効性が期待されます。
並列化
現在のところ、ベースとなるライブラリ iZ-C はシングルスレッドで動作することを前提に作成されています。 しかしながら、現在ではマルチコアCPUが一般的になってきており、特別に高価なハードウェアを用意しなくても 並列に動作するプログラムを動かすことが可能になりつつあります。
実際の業務に利用するプログラムの開発者としては、コストパフォーマンスの観点からも並列化が 重要になりつつあると認識しています。