ラベル設定法 先は未だ長い

 ようやくInstance13で、ラベル設定法によるLBが出るようになりました。下記は、LB＝1348までに到達するまでの時間比較結果です。

label setting algorithm:83sec

Current AL3:117sec

恐らく、幾多の研究者が、Instance13での求解に手間取った筈で、ラベル設定法によるLB解の提示が行われたのは、世界初と思います。ラベル設定法は曲者でして、数々の関門があります。その関門をくぐり抜けた者だけがInstance13のLB解に辿りつけます。ここまで来るにもかなり苦労しました。

しかしながら、さらに数十倍の巨大なインスタンス(instance22/23/24)に対しては、現在無力です。具体的には、

１）ラベル数の爆発が抑えられていない

２）求解時間がかかりすぎる　Instance23で300sec -3600sec/iteration

３）メモリ所要　11GB/roster

目標は、60sec/iterationですから、あと60倍程度高速化しないと使い物になりません。控えている改善アイデアをさらに投入すれば、なんとかなるだろうと見ていますが、それも未だ分からない、といった状況です。ちなみにMIPソルバによる求解では、2000secを下回ることはありません。