2020年4月27日月曜日

Instance20の新解が発見されてしまった

既に私が発見していたInstance20の新解が報告されてしまいました。4769は、既報通りで、正しい値です。

ぐずぐずしているからですね。Paperが準備中らしいので、興味深く、楽しみです。残されたインスタンスで未知で、未だ厳密解が報告されていないのは、Instance15/21/22..になってしまいました。Instance15は、報告していない新解を持っていますが、これが唯一となってしまいました。

Instance21/22については、線形ソルバーの高速化が必須で、私のところでも、厳密解に近いところを求めようとすると現状100日位かかってしまいます。

Instance23/24については、規模オーダが一桁違うので、Petter Strandmarkさんの手法か、メタヒューリスティクス等、別なアプローチが要ります。この辺は、数理ソルバーは、勿論、SATでも限界を超えていると思います。INRC2のようなダイナミックスケジューリングが、現実的アプローチになるのではないでしょうか?

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。