n100w8_0_0-1-7-8-9-1-5-4が解けた

 INRC2の難問インスタンスの内の一つの最適値が確定しました。これでOpen Instancesは、残り３となりました。

n100w8_0_0-1-7-8-9-1-5-4　LB:2030　UB:2030

です。

これを、解くのに4カ月かかってしまいました。これの何が難しいかというと、最適値である証明です。UB:2030は、比較的容易に得られますが、他にこれ以上良い解はこの世に存在しない、というのが大変難しいです。通常のBranch＆Boundでは、100万秒走らせたとしても証明は得られません。初期LB-UB　Gapは、１０以下であり、容易なように見えますが、実は難問中の難問です。

このインスタンスを解く努力を積み重ねることで、多くのことを学習し、また知見を得ました。で、このインスタンスで特徴的なのは、gap narrowing gain（私の造語）が極めて低いことにあります。その原因としては、構造的なsymmetryがあると思います。これを打ち破る方法としてsymmetry breakingがありますが、その方法については、また別な機会に。