MapReduce はPlanning問題を解くことができるか?

原文: Can MapReduce solve planning problems? by Geoffrey De Smet(OptaPlanner)

Planningや最適化に関する問題を処理する際、いくつかのソルバー(solver)は充分にスケールアウトしない傾向があります。問題に含まれる変数や制約が増えるほど、たくさんのRAMメモリーやCPUパワーが必要になります。数千個の変数があり、数億個の制約がマッチした段階でハードウェアのメモリー制限にヒットするでしょう。ハードウェア制限を回避する為、MapReduceをワークアラウンドの1つとして使うユーザーもいるようです。それでは、巡回セールスマン問題(Traveling Salesman Problem)のようなplanning問題をMapReduceしたらどうなるか見てみましょう。

MapReduceについて

MapReduceは、ビッグデータへクエリーするのにとても適していることが証明されているプログラミングモデルです。一般的には、次のように動作します:

• データが複数コンピューターノード間で分割されます
• map関数がすべてのパーティション上で実行され結果が返されます
• reduce関数は 2つの実行結果を1つに削減します。最終的に結果が1つになるまで継続的に実行されます

例えば、データクラスターの中から最高額の請求書を検索する必要があるとします。

• 請求書レコードは複数コンピューターノード間で分割されます
• 各ノードでは、map関数が該当ノードで最高額の請求書を抽出します
• reduce関数は2つの請求書を受け取り、より高額な請求書を返します

巡回セールスマン問題

巡回セールスマン問題(Travelling Salesman Problem(TSP))は基本的なplanning問題です。都市リストが与えられ、すべての都市を訪問する最短経路を見つける問題です。

例えば、ここに 最短経路が 674 である 68都市分のデータセットがあります。

この少数のデータセットによる探索空間は 68!(=10⁹⁶)通りです。とても広大です。

より現実的なplanning問題(例えば車輌の走行ルート案内など)は、さらにたくさんの複雑な制約を保有しています。例えば、車輌の積載量、車種による制限、期間、ドライバーの制限などです。

TSP を MapReduce する

68個の変数程度でメモリーが枯渇するソルバーはほとんどないと思いますが、小規模の問題を使うことで、きれいに視覚化し把握することが可能です。

それでは、MapReduceしてみましょう。

1)パーティション:問題を n個に分割します

初めに、問題を n個に分割します。一般的に n はコンピューターノード数となります。視覚的な理由から、今回は4つに分割します。

TSP は簡単に分割することができます。なぜなら1つしか制約(最短経路を見つける)がないからです。
現実的なplanning問題では、パーティショニングは困難であったり不可能な場合があります。例えば:

• 積載量を考慮した車輌経路探索では、2つのパーティション間で同じ車輌を共有しません。もし車両台数よりもパーティション数が多い場合どうしますか？
• 期間を考慮した車輌経路探索では、個々のパーティションは各地にドライブしてお客様へサービスを提供する為、充分な時間を持つ必要があります。矛盾: 走行ルートが未確定な状況で、どうやって走行時間を決定しますか？

2)Map:個々のパーティションで解く

各パーティションでソルバーを使い解きます

4つのパーティションは、それぞれ部分的な解答を算出しています

3)Reduce: 個々の解答を統合します

個々の解答を統合します。2つの解答を統合する為に、個々の解答からアークを削除し、パーティション間の都市を結ぶ為、アークを 2つ追加する必要があります。

統合処理を数回実施する必要があります。

個々の解答を結合する方法はいくつかあります。ここではすべての組み合わせを試し、最適解を適応しています。パフォーマンスを考慮し、個々の解答間でもっとも近接している都市をアークで結び、その後修正用のアークを反対側へ追加する(アークの追加作業は時間がかかるでしょう)方法もあります。

複雑な制約を含むより現実的なplanning問題で個々の解答を統合すると、実行不可能な解になることが多々あります。(制約違反(hard constraint)が発生します) すべての制約違反(hard constraint)が考慮された優秀なパーティショニングがされている場合、この問題を回避することはできるかもしれません。。。軽度の制約違反(soft constraint)が多数発生し、高いメンテナンスコストが発生するでしょうが。

4)結果: 実行結果の品質はどうでしょうか？

個々の解答は最適化されています。個々の解答は最適に統合されています。しかし、最終的な解答は最適ではありません。

実際には、MapReduceという手法でスケールアウトさせた結果は最適解と近い値ですらありません。

• 変数の増加は、解答の品質低下につながります
• 制約の増加は、分割し reduceできたと仮定しても解答の品質低下につながります
• 分割数の増加は、解答の品質低下につながります

結論

MapReduce はクエリー処理に適したすばらしいアプローチです。(クエリー処理以外でも、たくさんの問題に対して有効でしょう)しかし、planning や最適化問題に使おうとした場合、MapReduceはひどいアプローチです。適切なツールをこの処理に間しては使いましょう。

ノート: 今回は planning問題に MapReduce を使ってみました。意図を理解できるシナリオである為、ソルバーに実装された最適化アルゴリズムには使用していません。例えば、depth-first search アルゴリズムを使用した場合、MapReduce で探索木を探索するのは理解できるシナリオです。(探索木は指数関数的に悪いスケールをし、MapReduceによる効果を小さくでしょうが)

規模の大きい planning問題を解く際には、メモリーにより充分スケールするソルバー(optaplannerのような)を使いましょう。解答の品質を犠牲にしてパーティショニングに頼らないでください。

原文: Can MapReduce solve planning problems? by Geoffrey De Smet(OptaPlanner)