Lpソルバで緩和解

 以下は、スケジューリングベンチマークスの問題をLpソルバで解いたときの、時間です。SAT　Solveする際に、以下のルーチンをCALLしてLPファイルを作成→COPTのinteractive commandでMPSファイルに変換しています。

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

測定は、PDLPXで、GPUは、4060　16GBです。

ここで、着目するのは、Known　UBからは遥かに遠い値になってしまうということです。この状態からCutting Planeを駆使してUBまで持ってくるには、相当のMIP Solving技術がないとInstance8程度でも難しいです。（Highsでも1日程度かかります）

単純な緩和解との乖離が大きいというのは、ナーススケジューリング問題の本質的な難しさを示しています。

もう一つは、巨大なInstance23/24でもFirst Order Solver PDLPXは、難なく解けているということです。このあたりになると、MPSファイルで、2.4GBにもなります。COPTのバリアソルバでも解けない規模になりますが、難なく解けているのがPDLPイノベーションです。

どのようにしてSAT SolvingとLpソルバ緩和解を結びつけるか？というのが革新的核心技術になります。