グラフ縮約検討 その4

 Instance24を各Roster毎Highsで解いてみました。

Instance24の例えばStaff　BOは、次のような基数制約が記述されています。

これに対して、Highsで解いた結果が次です。

この結果は、例えば、Days１年後、a1というシフトは、最大で222であることです。optimalが1になっているので、最適解です。この結果は、他のRosterは我関せず、ですので、これ以上は、どんなことがあってもあり得ない、ということを示しています。

で、シフトa6に関してみると、最大値71に対して制約値も71最大になっています。この場合、a6に関して、制約値とHIGHS最適値が一致しているので、制約が効いていることを示しており、制約を削減することはできない、ということを示しています。

同様に殆どの制約で一致しており、制約を削減することは出来ません。唯一シフトs2だけが、制約値より小さくなっており、この制約だけは、なくても支障ない、と言うことが分かります。

instance21で見てみましょう。

この場合、シフトa2/p2/n1共、Highsの最適値は、39であり制約値46より小さいです。

つまり制約が効いていないことが分かります。instance21の場合、他のスタッフについても、同様な結果となっており、要するに全てのSecondary　Cardinalsは削除しても全く問題ありません。世界記録を提出したときも、このことを別な方法で分かっていたので、グラフ合成は全く行っていなくてPrimary　CardinalsのみのGraphで計算した解を提出しました。今回、Highsでも検証したのですが、Highsによっても裏付けが取れました。

このようにインスタンス毎、スタッフ毎に様相は、異なりますが、縮約の効果は期待できる場面もある、ということです。

なお、グラフだけの演算で解くことが出来ればそれに越したことはありません。今回HIGHSで最適解を解いていますが、instance21規模にしても結構な時間がかかっています。しかし、合成したグラフには、あらゆる最適解情報が詰まっており、一旦グラフ化が出来たならば、任意Daysの最適解は、経路探索によりほぼ瞬時に求まる、ということです。RCSPPの最適解は、グラフが出来たら即完了です。問題は、メモリにそのグラフを納めることが出来るか？の一点にあります。