LB-UB GAP どうやっても埋められない

 LBとUBのGAPがあるとき、UBは、厳密解とは言い切れません。これよりも良い解が、UB未満、LB以上の間に存在する可能性があるからです。この間の可能性を全て潰せたときに初めて現在のUB解が、厳密解であると言えます。UB解が厳密解である、と言い切るには、LB=UBとなる必要があります。

最終手段は、Branch＆Boundです。しかし、これが爆発すると、やはり現実的な時間内に厳密解を求めることができない、ということです。具体的には、計算機を２週間廻しても、行きつかない、行き着きそうな気配がない、という現象になります。

現在、次の４インスタンスだけが、厳密解証明が出来ていません。

n080w814-4-9-9-3-6-0-5

n080w820-4-0-9-1-9-6-2

n100w800-1-7-8-9-1-5-4

n100w812-4-7-9-3-9-2-8

色々策を講じたのですが、最後は、LB-UB　GAPがどうしても残っていしまいます。

そこで、計算パワーのさらなる強化を行うことにしました。具体的には、LPソルバのマルチスレッド化です。このテーマは、以前からあったのですが、中々手をつけられずにいました。

幸いにしてINRC2の構造はシンプル（フェーズとシフトが１対１対応でありタスクを含まないグラフ表現変換にすることが可能）なので、さらなる最適化が可能です。

グラフが簡素化されるので、LPソルバをマルチスレッド化した場合、複数のグラフリソースを持てるだけの余裕が生まれます。ロック機構が低減できるために、LPマルチスレッド化の効果を得やすくできるだろう、という筋書きです。結果がどうなるかは分かりませんが、後はひたすら時間をかけるだけ、という戦略に変更しました。出来れば8時間以内に全インスタンスの厳密解を目標にしていたのですが、それには拘らずに、とにかく厳密解が得られた、ということにフォーカスすることにしました。時代が進み、メモリとスレッド数を無制限に増やせば、いずれ8時間以内も可能になるだろう、ということです。

実装を行っています。時間を無制限にして　LB-UB　GAPを０、厳密解証明が出来るものと期待されます。今月中に実装、確認を行う予定です。

INRC2の厳密解証明が出来た後は、SchedulingBranchmarksの未解決問題２問に取り組む予定です。残念ながら、Highsの内点法ソルバ改善版が未だリリースされません。今月中にリリースされないようならCOPTに依頼する予定です。