[Tobs40]

Author here!

Did you read the entire article?

It's 271.666... moves, not 271.0 :) This bound comes from model where whole decisions (0 or 1) are relaxed to continuous ones (0.0 to 1.0 and anything in between), e.g. a piece can only be 0.23 there and only be 0.843 able to make a particular move. The advantage of this black magic is that it is way faster to compute and only overestimates the number of moves - hence we can use that to prove away bad partial solutions. Without a technique of this kind, searching the solution space would be absolutely intractable!

[dooglius]

I did read the entire article yeah, and I was rounding down with "271", but it wasn't clear to me what change you made that got you to the finish line. Are you saying that the next improvement was to force Gurobi to use integer values? It's surprising to me that wouldn't kill performance since ILP is NP-hard whereas real LP can be solved in polynomial time.

[salt4034]

This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218?

Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?

[Tobs40]

Ah, I see the misunderstanding.

I've always been solving the integer problem of course. But throughout the article, I improve the model formulation again and again through insights, which makes the LP relaxation tighter. Initially, it gave 305.0 as upper bound, but after tightening the model (addind constraints that cut off that 305 solution and others) it gives 271.666...

- which leads to insanely faster search. It's like brute-forcing through all passwords of length 20 and a wizard telling you that you're wrong when you reach character 7 instead of 13.