4 ms·
Is the solver guaranteed not to land in a local minima/maxima?
by alexchamberlain 1y ago
Is the solver guaranteed not to land in a local minima/maxima?
- moralestapia 1y ago(I don't know) But I would guess the answer is "no". If you can prove, as they claim, that you have an algorithm that gives you the optimal solution (aside from the obvious, brute-forced one), you might be one stone throw away to make an argument for some P == NP, that would be HUGE. But it seems that some people get offended when you tell them their perpetual motion machines are not real.
- unnah 1y agoThe branch-and-bound algorithm does provide a proven optimal solution. This does not mean that P=NP because the size of the proof is not bounded by a polynomial in the input size, and neither is the algorithm runtime. Also, Euclidean TSP is known to be easier than TSP on arbitrary graphs: there are polynomial-time approximation schemes that can produce solutions with an (1+epsilon) factor of the optimum in polynomial time, for any value of epsilon. Thus it is not surprising that a proof of full optimality can be constructed for some instances.
- inasio 1y agoThe solver generates a relaxed lower bound that indicates how far they could be from the global optimal solution. The moment that the lower bound improves enough to match a path they can guarantee that it's the global optimum