Remix.run Logo
dbatten 5 hours ago

Genuinely interested in being educated here: If Gurobi's integer programming solver didn't find a solution better than 218, is that a guarantee that there exists no solution better than 218? Is it equivalent to a mathematical proof?

(Let's assume, for the sake of argument, that there's no bugs in Gurobi's solver and no bugs in the author's implementation of the problem for Gurobi to solve.)

I guess I'm basically asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.

salt4034 4 hours ago | parent | next [-]

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 4 hours ago | parent [-]

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 4 hours ago | parent | next [-]

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!

hyperpape 5 minutes ago | parent | next [-]

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

dbatten 3 hours ago | parent | prev [-]

> 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...

3 hours ago | parent | prev [-]
[deleted]
gregdeon 2 hours ago | parent | prev | next [-]

I'm not sure about Gurobi or how the author used it in this case. But in general, yes: these combinatorial solvers construct proof trees showing that, no matter how you assign the variables, you can't find a better solution. In simpler cases you can literally inspect the proof tree and check how it's reached a contradiction. I imagine the proof tree from this article would be an obscenely large object, but in principle you could inspect it here too.

nhumrich 4 hours ago | parent | prev [-]

In theory, it's not proof. In practice, it is.

sigbottle 3 hours ago | parent [-]

Well, if the solver isn't wrong and there were no bugs in impl, yes, the approach is rigorous. Allow strictly more "powerful" configurations yet still prove that the maximum is X, then achieve X through a construction, is standard math