instance24 UB＝40439を得た

超弩級問題instance24の解を得ました。

LB-UB GAPは、約0.00247%　となり、ほぼ最適解を得ることができました。このベンチマークが提出されたのは、十数年前になります。今まで、幾多の研究者がこのベンチマークに挑んできましたが、ここまで最適解に近接したことはありません。(前世界記録は、理論上の最適解まで17%余りでしたが、今回の結果は、0.00247%まで迫っています。3桁以上の高精度を達成）

 LB:40438　UB:40439

Instance24 Solving History

Machine: Ryzen 9700X　192GB Memory  RTX5070TI GPU with COPT 8.03 Barrier Solver

この問題の何が超弩級かというと、シフト数が32もあり、それに対して全Dayで、これに対するCover制約がほぼMaxとMinで存在する、ということです。それが、364日x32シフト分のソフト制約があるので、約12000本のCover制約があることになります。市井のナーススケジューリング問題は、長入明と、早遅番日勤ぐらいでしょうから、6（シフト）x31（日）＝精々186本程度で、桁が二桁程違います。

下記に、解の一部を示しますが列ソフト制約のスラックは、最大で20近くに達します。

AutoRosterが示す探索空間は、１０の82911乗になります。とにかく、とんでもない規模の問題になります。これを解くソルバを開発設計するのに1年半もかかってしまいました。

論文化を予定していますが、整数化の最後に、新開発のMaxSATソルバで0.25secで解けている様子を示します。

ちなみにWCNFを生成させていますが、2026MAXSAT優勝ソルバApertureでこのWCNFを解かせても、全く歯が立ちません。UB＝1億2500万のところでスタックしてしまい、3日経っても進行しません。

尋常な方法では、まったく歯がたたない世界、それがInstance24です。

HardWare資源もGTX1660→RTX4060TISuper→RTX3080→RTX5070TI,Memory　64GB→128G →192GBと増強してようやくたどりつくことができました。Lpソルバも尋常な規模ではありません。世界一のBarrierSolverを持つCOPTに評価ライセンスの延長をお願いし協力を得ることができたおかげでもあります。COPT SUPPORTに感謝申し上げます。