グラフコンパイル問題

 各スタッフの制約を全てグラフ化することは、現在のメモリで難しいので、次善の策として、以下を検討しました。

１）MIPソルバで解く

HIGHSで解いてみましたが、遅すぎて使えません。ただし、ROOT　LB時のみ使用する、アイデアはあります。

２）基数制約を主問題に移す

主問題のLpソルバの負担大となる問題点があります。また、概算値を高速に得る手段としては、有望ですが、今回の要件は、厳密解を得ることにあり、その面では何ら解決策にはなりません。厳密解を得るには別な手段が必要です。

３）基数制約をコンパイルしないでグラフ化、列生成問題として解く

この手段は、前にも行っていて(instance22の世界記録提出で使用）有望なのですが、厳密解を得るという意味においては、苦しいです。加えて、Instance24では、やはり遅すぎて使えませんでした。

４）部分的に基数制約をグラフ化、列制約問題として解く

最終的に残った候補です。基数制約の全てをグラフ化することはメモリ的にアウトなので、支配的性質を持った基数制約についてのみ着目してグラフ化します。この方法は、厳密解を得易く、しかも３）よりは遥かに高速で有望です。しかし、instance24のたった一つの基数制約をコンパイルするにも128GBメモリでは出来ませんでした。

そこで、4)のグラフをコンパイルするべく、メモリ増強を行いました。