読者です 読者をやめる 読者になる 読者になる

最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

空白セルの圧迫と「ルール」の力

「一筆書き」のように、 答を見せられれば正しいかどうかはすぐにわかるけれど、 「白紙」の状態からそれを見つけるのはかなり難しい、 というタイプの問題は世の中には数多くあります。 数学的な話で有名なのは大きな数の素因数分解ですが、 ここまで抽象的な例を引っ張り出さなくても、選択式の試験よりも記述式の方が難しい、とか 日常的な感覚として了解できるところかなと思います。

じつはこの手の「一筆書き」的問題にアプローチできるという点が数理最適化という手法の特徴の一つと言えます。 次はマス目タイプのスケジューリング問題のデモンストレーションで、20人の一か月分のスケジュールですが、 水色のセルに(準日勤、日勤、準夜勤、当直、深夜勤、休日)のいずれかを入れる、 というのがここでの課題になります。 入力は、各日に各勤務を担当している人の合計人数(タテ計)と各人の休日数(ヨコ計)で 黄色い表の部分です。

f:id:optimizationTanabe:20160824121716p:plain

しかしこうしてみると水色の空白セルから受ける「圧迫感」はかなりのものです。 マス目タイプのスケジューリング問題は制約の数(表のタテヨコの和)よりも変数の数(表のタテヨコの積)が圧倒的に大きくなるのでやむを得ないことではありますが。実務家の方々が、毎月この空白セルを手動で埋めていると考えるとその労苦が偲ばれます。そんなところに数理最適化が現れてこんな答を書き込んでゆきました・・。

f:id:optimizationTanabe:20160824121756p:plain

ときにつっこみどころ満載ではありますが一応制約を満たす答ではあります。一つの結果があるとこれがいわゆる 'ice break' になって思考を前に進めることはできます。

こんなことを計算機がやるなんて、なんかちょっと不思議?

そうですね。 このシフト表を与えられて集計結果を出すのは計算機がごくあたりまえに行うことですが、 逆に集計結果しかない状況でシフト表を計算機に求めさせようとするのが数理最適化なのです。

データが潤沢に得られる「ビッグデータ時代」になって、 計算機ができることの質が格段に向上したのは確かなのですが、 だからと言ってデータが不足している場合に何もできないわけではありません。 データの不足は「ルール」で補うのです。上のケースでは、集計結果を合わせることと、 勤務種別に関する幾つかのルール(実は最初の二行に対応する人、1番さんと2番さんには日勤優先、としています)、 そして努力目標(休日の日数はできるだけ揃える)を与えるだけでかなりもっともらしい勤務表を導くことができています。

もちろん、「ルール」一辺倒で事足りるわけではないのは、大量データの解析を背景とした昨今の機械学習の応用の目覚ましい発展が教えるところであります。一般に「ルール」は各論的な話や明文化できないものに弱い。 ルールの目が粗すぎると結果が絞り切れてなかったり、 逆に細かすぎても前回議論したような実行不可能性が引き起こされて結果が出なくなってしまうこともあります。 そんなときには「ルール」に拘りすぎずに過去の勤務表の「データ」を使うのが最善の手です。 シフトの例で言えば、もし過去の勤務表がデータ化されているのなら、将棋のプログラムで使われているように 何等かの評価値(結果が前例のように尤もらしいか)を作成して、シフト生成の目的関数に利用する、といったことができます。数理最適化の立場としては「データ」あるいは「モデル」一辺倒ではなく、手に入る限りの「データ」と「モデル」両者から、うまく情報を引き出して要領良く適切な結果を得ることが現在の我々に求められていると言えるでしょう。