グラフ縮約の検討その３

■Scheduling　Benchmarksのinstance22では、PrimaryCardinals制約は、コンパイルできるが、他のCardinals制約と合成コンパイルが出来ない　（96GBメモリ）

■instance23では、PrimaryCardinals単体でも、コンパイルが出来ない

という問題があります。これに対処する案の検討を行いました。

Scheduling Benchmarksは、全て同じ形態であり、

業務時間累計に対して最大・最小を規定しています。(Primary Cardinals制約）

これに対して、個別のシフト群に対して、シフトパターン数最大のみを指定しています。(Secondary Cardinals制約）

さらに、最大連続勤務日数、または、最小連続勤務日数が既定されています。これらは、スタッフ固有の規定です。

さらに、シフトパターンが、規定されています。これは、スタッフ共通です。

また、スタッフ毎にあり得るシフトが（ランダム的に）規定されています。

また、ハード予定があります。

Scheduling　Benchmarksで有難いのは、これらが全てハード制約で記述されている点です。ソフト制約ならば、解空間を削減することは出来ないのですが、ハード制約なので、解空間を限定的にすることが可能になります。

１）Sencondary　Cardinalsの削減

Primary　Cardinalsは、業務時間累計の最大ー最小を規定しています。Secondary Cardinalsを全て除いた条件で、Secondary Cardinalsの最大値を求めるものとします。これは、他のスタッフを参照することなく、個別Roster毎に求めることが出来ます。ソフト制約ならば、全体品質との兼ね合い部分が出てきてほぼ、求めることは出来ませんが、ハード制約のみで記述されているので、個別Roster内に限定して求めることが出来ます。小さい規模のＭＩＰ問題となるので、内蔵Highsで解くことにします。

２）存在意義があるSecondary　Cardinalsを含めた条件下で、Secondary　Cardinalsの最大ー最小を求めます。これも内蔵Highsで解くことにします。

３）Primary-Secondaryの同時コンパイル

問題は、最適性の緒元を失わずに、如何にグラフを縮約するか？にあります。グラフの合成段階でも、コンパイルエラーが発生しているので、合成によって最大規模演算になっている可能性があります。このように合成された結果が小さいものであったとしても、合成される過程で一時的に大きくなりすぎてしまう問題は、しばしば遭遇します。この問題に対して、

同時コンパイルが出来れば、合成そのものを排除出来ます。また２）で求めた条件を入れこめば、グラフ状態数をより削減できるのではないか？と思われます。

業務時間累計は、全てのシフトに対する時間和となる関係であり、独立問題ではないハード制約です。よって、業務時間累計を求める過程において、各シフトのMin-MaxでPruneすることが可能になります。

４）それでもダメなら、２）で中間ゲートもさらに求め、さらに状態数を削減します。

この案の胆は、個別Roster毎にグラフ縮約が可能になる、ということです。個別Roster毎に限定したオペレータであり、何ら最適性を失なうことがなくグラフ縮約が可能となります。結果として、コンパイル出来る可能性が高まります。これは、スケジューリングベンチマークがRosterに関しては全てハード制約で記述されているおかげです。結果、6カ月や1年という長い期間のコンパイルが可能になるのです。

言い換えれば、INRC2のようにソフト制約が入りまくりのベンチでは、今回の手法は、全く意味をなさないので適用することはできません。逆に、今回のような手法が使えないので、INRC2で6カ月や1年というベンチマークは、規模が大きすぎて全く解けないレベル、と言ってよいと思います。

実務ベンチは、どちらかと言えばINRC2に近いソフト制約が主だと思いますので、2025時点のコンピュータリソースでは、NSPが現実的に解ける規模は、高々２－３カ月以内の規模程度、ということが出来ます。