新しい解の発見

ほとんどのインスタンスは、既に解かれてしまっています。

解のOptimumが未知のインスタンスは、あまりありません。狙い目は、解かれていないInstance15、そしてInstance19以上です。Instance19以上は、超巨大なインスタンスで、開発中のソルバーも、悪戦苦闘していますが、このレベルだと、現在、コンパイルすら通らない有様です。ところが、Instance15は、なんとかなりそうなのでやってみました。

今日現在、
http://www.schedulingbenchmarks.org/

のインスタンス15のKnownBestValueは、3834です。この値は、Pieter Smet さんが10時間回したBest値です。

数時間回したら、3831を発見してしまいました。この解は、多分、人類未踏の解です。ナーススケジューリングの歴史に名を残せそうです。

大規模インスタンスに対する改善を行って、他のインスタンスについても新しい解を得ることが6月の目標です。実は、このベンチマークのインスタンスは、実務から言うと特殊でして、このインスタンスセットについて、飛び切り優秀だとしても実務インスタンスの性能向上にはほとんど役にたちません。実務インスタンスに応用するには、もう一段手を加える必要があります。それが終了して、製品化実装を行って、初めて世にでることになります。発想から一年以上かかっています。