シフト最適化アルゴリズム

 下は、2017年にRAMPで使用したスライドです。

早いもので、これから8年が経ちました。シフト最適化に良いアルゴリズムは何か？というのは、私が、10年以上追い求めているテーマで、この講演時から、SATソルバの限界を感じていてMIPソルバの勉強を始めました。終生の目標として、未解決ナーススケジューリング問題を全問解くという、前人未到の目標を掲げて研究に取り組んできました。

このときは、感触でしかなかったのですが、今は、割に確信に近いイメージを持っています。一つの方式で全てのインスタンスを包含する最適アルゴリズムは存在しない、というイメージです。

＜メタヒューリスティクスは無くならない＞

ナーススケジューリング問題の黎明期は、メタヒューリスティクス開発の全盛期で、その後次々と、ベンチマーク問題がMIPソルバにより解かれ、メタヒューリスティクスは駆逐されたように思われています。確かに、そうした面はあります。

が、実務問題で厳密解が得られているか？という問いに対して、実は、スケジュールナースでも、最近は凝った制約の塊になることが多く、例えば、5年以上使いこなしているお客さまのプロジェクトを見ても、複雑化した制約が追加され、厳密解が得られることは、多くはない、という傾向が強まった、と思っています。

そして、超大規模のインスタンスに対しては、依然として、現実時間内に現実的な解を得るには、メタヒューリスティクスに頼らざるを得ない、ということではないかと思います。

学生さんがよく取り上げるテーマですが、既にベンチマークセットがあるので、それに対してどうだ？という比較で論じて欲しいと思います。単に実務問題で解けた、では価値がないと思います。

＜SATソルバが得意なインスタンス傾向＞

SATソルバは、数を数えるのが苦手です。線形制約は、全てブール演算から構成する必要があります。逆に言えば、数を数える場面がない、もしくは少ない場面では、無類の強さを発揮します。例えば、数独もその一つです。100x100の数独問題を解けるのは、今も昔も今後もSATソルバだけだと思います。そのような傾向の強いインスタンス、組み合わせ最適化問題には、SATソルバが最適です。

もう一つの傾向として、

■解空間/探索空間の比率が高いとき

に強さを発揮する傾向にあります。平たく言うとソフトエラーの数が少ないインスタンスは、強いということです。池上ベンチは、全ての制約がソフト制約で、その意味では、探索空間の枝刈りを行うことは出来ません。そのため、探索空間は確かに膨大なのですが、解空間も意外に広い、解の範囲が広範囲に分布しその比率は意外に高いのです。

こうしたインスタンスには探索中の学習が効果を発揮し、高速に求解出来ます。

＜MIPソルバが得意なインスタンス傾向＞

MIPソルバは、基本線形制約（SATソルバでいう基数制約）で記述します。AND/ORという非線形演算子は備えていないので、そういったオペレータが多いインスタンスは苦手です。で、何が得意かというと、

■数を数える

■解空間が狭い問題

が得意です。SATソルバが苦手な分野を補完しえるということです。Simplexや内点法といったLpソルバのリニア解を近傍探索するアプローチを取っています。基本、数を数えることしか出来ないのですが、それでも人間が作るインスタンスは、リニア解が近い傾向があり、解空間が狭い、地球上の一つの砂粒を探しだすような最適化問題には、LPソルバをベースにした方法しか考えられません。人間が扱うような問題は、リニア解近傍に最適解が存在することが多い、ということを前提としています。SATもMIPもランダムな制約には、全く持って歯が立たないのですが、現実の人間の営みのなかにあるエントロピーがそうさせているのでは？と考えています。

＜ナーススケジューリング問題についてあてはめると＞

スタッフ一人一人をRosterと言います。スケジュールナース用語では行制約ですが、Roster内演算は、多数のAND/OR演算が主で、僅かに公休数とか夜勤数といった数を数える場面があります。

一方、組織の品質を求める縦制約（列制約）については、ほぼ数を数えるだけです。つまりLPソルバにやらせた方が得策、ということになります。

従い、Rosterをサブ問題として、AND/OR演算を隠ぺいし、列制約を主問題としてLPソルバで扱うのが、一般的ナーススケジューリング問題に対する理にかなったアプローチ、ということが言えます。

＜今後の潮流＞

MIPでもなくSATでもない、否、MIPでもありSATでもある、新しい形態の数理ソルバが今後の厳密解ソルバの主役になっていきます。

現在、超大規模用にRefineする必要があり、一つ一つの求解部品を丹念に設計し直し組み上げていく作業の途中です。

オープン問題を全問解いたあとに論文化を予定しています。10年の研究成果が出るかどうかは未だ分かりません。

厳密解が分かれば、新しいメタ解法の開発に役立つと期待されます。