日~土を指定があります。まともに実装するのは面倒なので、夜呼び出し間隔で1週間未満を禁止にする方が簡単です。この方式は、1週間未満のあらゆる2回を禁止するので、題意の仕様を含んでいます。
このプロジェクトの場合は、呼び出しは、タスクなので、以下のように実装しています。
日~土を指定があります。まともに実装するのは面倒なので、夜呼び出し間隔で1週間未満を禁止にする方が簡単です。この方式は、1週間未満のあらゆる2回を禁止するので、題意の仕様を含んでいます。
このプロジェクトの場合は、呼び出しは、タスクなので、以下のように実装しています。
DDR5は、4枚刺しは、推奨されていないようです。実際48GBメモリ2枚+16GBメモリ2枚では、起動しませんでした。
DDR5の異サイズ4枚刺ししてみた #自作PC - Qiita
マザーボードのマニュアルにも同一ロット4枚刺しが記述されていたのですが、同一メーカ品の同一仕様4枚,4x48=192GBで、何とか動いてくれました。
しかし、やはり同じに動いているようではないようです。
これからAIをローカルで試してみたい方は、GPUはなしとしても、メインメモリは32GBでは不足すると思うので要注意です。
メモリ問題から、全基数制約をコンパイルするのを諦めて、TIME制約とWEEKEND制約のみコンパイルします。
そうしたときに要するRoster1個あたりのメモリ所要量です。
コンパイルメモリ所要 コンパイル時間 グラフメモリ所要量
instance23 48GB 45分 0.7GB
instance24 140GB 2-3時間 1.5GB
このために、メモリを32GB⇒48GB⇒96GB⇒192GBまでDDR5を増量しました。instance23で、グラフコンパイルだけで、丸2日、instance24で2週間程度かかります。
<コンパイル時間問題>
こんなに時間がかかるなら、別な方法を検討したくなりますが、実は、この問題は、クラウドを使えば現在でも解決できます。というのは、スタッフ毎に独立してコンパイルが可能だからです。リソース無尽蔵のクラウド資源を使えば、並列にコンパイル可能です。つまり、リソースさえ気にしなければ、全スタッフを2時間でコンパイルは出来ます。
<コンパイルメモリ問題>
グラフのコンパイルに192GBメモリが必要です。AIに10年後の予測をしてもらったところ、AI需要等により64-256GBになるとのことでした。
よって、10年後では、標準的なPCで十分に対処可能になると予測します。
<グラフメモリ問題>
instance24は、150staffなので、平均1.5GBだとすると1.5*150=225GB > 192GB で足りません。
Diskに退避した場合、現在の高速SSD+対応ボードを使うと14GB/secの転送レートで、メモリ転送レートと比べて、そんなに遅くはありません。以前のHDDを使った転送レートと比べれば雲泥の差です。それでもGraph処理レートよりもDisk転送レートの方が遅い可能性が高いので、できるだけメモリ上で圧縮処理した方が得策とみます。
<グラフ縮約>
一度LBが算出されれば、後は、厳密解に拘る必要はありません。つまりLB算出までは、Fine、それ以降は、Coarseで制御します。グラフ処理速度は、グラフ規模で一意に決まるので、グラフを極小化することで、処理速度を向上させます。
まとめると、
LB算出までは、厳密解を得るために、多少時間がかかってもグラフの縮約は用いません。
LB算出以降は、実用的なBranch&Bound速度とするために、グラフの縮約を用いて高速化を図ります。
以上の検討により,
■instance24のコンパイルに192GBメモリ48x4
■必要ならば、メモリ上でグラフ圧縮処理
■LB算出後のグラフ縮約
を行うこととします。
さすれば、グラフメモリ問題は解決できる、と結論します。
とりあえず、instance24のグラフメモリをDISKに保存中です。この予備処理に2週間程度かかる予定です。一旦グラフメモリを保存することが出来たならば、後はそれを用いてさらにアルゴリズムの検討を行うことが出来ます。HIGHSの新IPMは、GITHUBを見るとかなり期待出来る速度となるようです。これにより、課題要素は、それぞれクリアできるのではないか?と期待されます。
各スタッフの制約を全てグラフ化することは、現在のメモリで難しいので、次善の策として、以下を検討しました。
1)MIPソルバで解く
HIGHSで解いてみましたが、遅すぎて使えません。ただし、ROOT LB時のみ使用する、アイデアはあります。
2)基数制約を主問題に移す
主問題のLpソルバの負担大となる問題点があります。また、概算値を高速に得る手段としては、有望ですが、今回の要件は、厳密解を得ることにあり、その面では何ら解決策にはなりません。厳密解を得るには別な手段が必要です。
3)基数制約をコンパイルしないでグラフ化、列生成問題として解く
この手段は、前にも行っていて(instance22の世界記録提出で使用)有望なのですが、厳密解を得るという意味においては、苦しいです。加えて、Instance24では、やはり遅すぎて使えませんでした。
4)部分的に基数制約をグラフ化、列制約問題として解く
最終的に残った候補です。基数制約の全てをグラフ化することはメモリ的にアウトなので、支配的性質を持った基数制約についてのみ着目してグラフ化します。この方法は、厳密解を得易く、しかも3)よりは遥かに高速で有望です。しかし、instance24のたった一つの基数制約をコンパイルするにも128GBメモリでは出来ませんでした。
そこで、4)のグラフをコンパイルするべく、メモリ増強を行いました。
Q.下図のようにしたいのですが、上手く行きません。
| AM(ph0) | PM(ph1)
| 作1,作2 | 会
=================================
早番 から作業1を 2名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
遅番から作業2を1名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
日勤 から作業2を1名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
Q.
例えば、No1で作業所1早番は早番可能な職員を午前中に作業場所1のタスクを最大2名配置そしましたが、これは午後には配置しないと同義にはならず、午後に配置したくなければ、No2のように午後は禁止とすることが正解なのでしょうか?