個々のRosterの時間計数和の最大・最小を求める

 問題を解く前のPreconditionを求める問題です。時間制約は、MDDで解くことにしましたが、未だ規模が大きすぎるので、小さくすることを検討しました。個々の時間計数和で規制できれば、大幅にMDDサイズを小さくできます。

https://schedule-nurse.blogspot.com/2026/02/mdd_14.html

１）個々のRosterの簡易モデルをMIPソルバで解く

詳細モデルまで含めてHighsMIPソルバで厳密解を求めるのは難しいです。仮に求まったとしても、個々のRoster空間しか見ていないので、最小0、最大時間制約値となってPreconditionの意味をなさない可能性があります。

２）全体LPの最大・最小問題として解く

前回の検討で、GPUを用いたPDLPXであれば、全体目的関数値AがReasonableな時間内に求まることが分かりました。

https://schedule-nurse.blogspot.com/2026/02/cnf2lp.html

https://schedule-nurse.blogspot.com/2026/03/lp.html

今真値UBは、当然分かっていないのですが、あり得るUB値Ｃでカットオフし、目的関数を個々の係数和の最大・最小問題に置き換えます。今係数は、４，５，６の3種類、最大最小でｘ２、150人で、ｘ150回、＝900回求解すれば、全体ＬＰで規制される（目的関数値Ｃ以下）条件化における、あり得る最大最小値が、Preconditionとして導入することが出来ます。この範囲が狭ければ狭いほど、MDDサイズを小さくできます。個々の空間しか見ていない１）に対して、緩和解ではあるもの全体空間を見ているので、１）よりは小さくできるものと期待されます。

問題は、あり得るUB値Cにあります。それは仮定であるということになります。最終的に、首尾よくUBが求まった場合のみ意味あるということです。A値は、緩和解における目的関数値であり、真値UB　Bが数万に対して、Aは、数千に過ぎません。間違ってもA値でカットオフしてはいけません。