どの変数から値を当てはめるか、変数に対して候補の値をどれから当てはめるか(あるいはどの値ではないとするか)によって問題を解く速さに大きな差が発生する例を、ジョブショップスケジューリング問題で示します。
探索戦略とは
制約プログラミングでは、変数が取りうる値を制約を用いて効果的に削減することができます。このために用いられるメカニズムには「制約伝播」のようなものがありますが、全ての値の候補を削除できるわけではありません。 そうなった場合、変数に値を当てはめてみて矛盾が生じないかどうかを順番にチェックしていく必要があります。
この時、どの変数から値を当てはめるか、変数に対して候補の値をどれから当てはめるか(あるいはどの値ではないとするか)によって問題を解く速さに大きな差が発生することが分かっています。
変数を選択する戦略としては、First Fail Principle というものがよく知られており、これは「最も値を当てはめがしにくいものを最初に選ぶ」というものです。具体的には「最も候補となっている値が少ない変数」や、「最も多くの制約が付与されている変数」などがこれにあたります。また、探索中に実際に失敗(fail)が生じたかどうかで動的に変数選択順を入れ換えるような戦略も提案されています。
変数に当てはめる値を選択する順序としては、「最も制約を満たす見込みが高いもの」が先になるようするのが自然ですが、これについては First Fail Principle 程に一般的なガイドラインはないようです。(当然ながら、問題固有の性質を利用することは可能です)
このように制約だけでは決定しきれない変数の値を決定していくための戦略が探索戦略ということになりますが、高度なものでは一旦失敗すると分かった値の組み合わせは次回から使用しないようにするなど、実際に問題を解くプログラム(ソルバと呼ばれます)では様々な工夫が凝らされています。
ジョブショップスケジューリング問題
ジョブショップスケジューリング問題とは、工場などで必要となる問題を抽象化したもので、以下のものが与えられます。
いくつかのジョブ。ジョブは異なる機械を決まった順番で決まった時間だけ使用することで完了します。 異なる機能の機械。機械は一度に一つのジョブしか処理することはできません。 この条件の下で、すべてのジョブが完了するまでの時間を最小にするというのがジョブスケジューリング問題です。 (この単純にモデル化された「ジョブショップスケジューリング問題」では現実の問題とは異なり、ジョブを切り替える際の段取り時間などは考慮されないのが普通です)
この問題はジョブや機械が増加すると調べなければならない組み合わせが爆発的に増加してしまうため、現実的な時間で最適解を求めることが難しいとされています(NP困難として知られています)。
外部のサイトとなりますが、ORWiki 《スケジューリング問題》 にも詳しい説明があります。
制約プログラミングとの関連
ジョブショップスケジューリング問題はNP困難問題とされてはいますが、これは任意の問題について厳密に「最適解(最小時間)」を求めるのが難しいということを述べているものであり、「特定の性質を持った問題を解くこと」や「近似解(最小ではないが十分に小さい時間となるような解)を求めること」であれば実用的な時間で行える可能性があります。
また、現実の産業的な応用が期待されることもあって、古くからさまざまな手法が提案されてきました(遺伝的アルゴリズムに代表される進化的アルゴリズム, タブーサーチのような近傍探索に基づく手法など)。
さらに、ジョブショップスケジューリング問題そのものは機械の使用順序や使用時間の制約で記述された問題であり、制約プログラミングを用いた求解も可能です。これはジョブショップスケジューリング問題を制約最適化問題 (Constraint Optmization Problem, COP)としてとらえるやりかたです。
現実の問題では、単純なジョブショップスケジューリング問題では省略されている制約(例えば段取り時間)が必要とされることもあり、そのような場合には制約を一般化して記述できる制約プログラミングは大きなアドバンテージを持つことになります。しかしながら、元々解くことが困難な問題であるため、実際に解く為にはソルバの探索戦略が重要になってくる訳です。
デモンストレーション
問題について 制約プログラミングのためのパッケージ MiniZinc にはベンチマーク用にさまざまな問題が含まれています。この中にジョブショップスケジューリング問題のベンチマークとしてよく用いられる問題が含まれているため、このうちの一つ、“la01"を取り上げました(比較的解くのがやさしい方の問題ではないかと思われます)。
デモについて ソルバでは、実際の最適解が求められる前に、制約を満たす解をいくつも求めています(ジョブショップスケジューリング問題では、全てのジョブが終了するまでの時間が徐々に改善された解が求められることになります)。デモでは途中経過を視覚化することで、探索戦略の違いが最適解を求めるまでの経過にどのような影響を与えるかを分かりやすく示しています。
なお、このデモでの目的は途中の解を順次提示することであって、解が求められるまでの時間は実際の求解時間とは異なります。
また、ブラウザの機能を使用してアニメーションを行っているため、SVG および JavaScript をサポートしている必要があります。Internet Explorer (IE)の場合は IE9以降が必要です。Chrome, FireFox といったブラウザでは比較的新しいバージョンであればサポートされているようです。
単純な探索戦略
定義された変数順、定義された値順に探索を行った場合の挙動について示します。ジョブの番号の若い方から順番に詰め込みが行われている様子が分かります。
(FlatZincソルバとしてはデフォルトの g12fd が用いられています)
その他の探索戦略
動的な変数選択順やローカルサーチ、ランダムリスタートを組み合わせた探索を行った場合の挙動について示します。計画が全体的に組み替えられる様子、似た解を探してしまって改善が滞る場合がある様子が分かります。単純な探索戦略よりは早い段階で良い解が得られる傾向にあります。
(FlatZincソルバとしては2013年版の izplus が用いられています。izplusの解説はこちら)
まとめ
制約プログラミングで難しい問題の解を求める時には、適切なモデル化とともに探索戦略も考慮する必要があります。ここでは難しい問題の代表例としてジョブショップスケジューリング問題を取り上げ、異なる探索戦略を用いた場合に最適解にたどり着くまでの様子が異なることを示しました。
実際の応用例では問題の性質に着目した探索戦略を用いる場合もありますし、汎用的な探索戦略で十分な場合もあります。制約プログラミングではモデルを記述する能力や制約伝播を用いた探索空間の削減に注目が集まりますが、実際に問題を解くにあたってはさらに探索戦略も重要となることをご理解いただければと思います。