[salt4034]

In addition to the value of the best integer solution found so far, Gurobi also provides a bound on the value of the best possible solution, computed using the linear relaxation of the problem, cutting planes and other techniques. So, assuming there are no bugs in the solver, this is truly the optimal solution.

[dbatten]

Unless I missed something, though, the highest bound the author reported for the relaxation was 271 2/3 moves, which is obviously significantly higher than 218...

[salt4034]

I think that was an intermediate model. The author updated it, then Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).

> With this improved model, I tried again and after ~23 000 seconds, Gurobi solved it to optimality!

[dbatten]

> Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).

Ah, I was not aware that that's what this language indicated. Thanks for helping me understand more!

I've used Gurobi (and other solvers) in the past, but always in situations where we just needed to find a solution that was way better than what we were going to find with, say, a heuristic... I've never needed to find a provably optimal solution...

[hyperpape]

The article was interesting, but this bit felt a bit like "and then a miracle occurred".

[chipsrafferty]

The fractional stuff was poorly explained, I didn't understand it at all.