One more P=NP proof?

Abtract. We present a polynomial-sized linear program (LP) for the \(n\)-city TSP drawing upon "complex flow" modeling ideas by the first two authors who used an \(O(n^9) \times O(n^8)\) model^*. Here we have only \(O(n^5)\) variables and \(O(n^4)\) constraints. We do not model explicit cycles of the cities, and our modeling does not involve the city-to-city variables-based, traditional TSP polytope referred to in the literature as "The TSP Polytope." Optimal TSP objective value and tours are achieved by solving our proposed LP. In the case of a unique optimum, the integral solution representing the optimal tour is obtained using any LP solver (solution algorithm). In the case of alternate optima, an LP solver (e.g., an interior-point solver) may stop with a fractional (interior-point) solution, which (we prove) is a convex combination of alternate optimal TSP tours. In such cases, one of the optimal tours can be trivially retrieved from the solution using a simple iterative elimination procedure we propose. We have solved over a million problems with up to 27 cities using the barrier methods of CPLEX, consistently obtaining all integer solutions. Since LP is solvable in polynomial time and we have a model which is of polynomial size in \(n\), the paper is thus offering (although, incidentally) a proof of the equality of the computational complexity classes "P" and "NP". The non-applicability and numerical refutations of existing extended formulations results (such as Braun et al. (2015) or Fiorini et al. (2015) in particular) are briefly discussed in an appendix. [^*: Advances in Combinatorial Optimization: Linear Programming Formulation of the Traveling Salesman and Other Hard Combinatorial Optimization Problems (World Scientific, January 2016).]

https://arxiv.org/abs/1610.00353

Unfortunately there are about as many \(P=NP\) proofs around as there are \(P\ne NP\) proofs. See (1) for a large list. The first author is already on the list with a few earlier papers.

As a practitioner, all of this may not be so important, but there are cases where I see complexity theory being somewhat misused or misunderstood in the following sense. When confronted with a combinatorial problem, a common reaction is to a-priori dismiss Mixed Integer Programming in favor of some heuristic, often accompanied with some mumblings about NP-hard problems. I believe complexity theory says very little about solving a given problem of a given size with an actual MIP solver. Notice also that many state-of-art MIP solvers contain many heuristics. In practice, for large difficult problems, MIP solvers can often (but not always) deliver good solutions quickly, with the added advantage of giving you an indication of how close we are from a possible optimal solution (the gap).

References

1. Gerhard J. Woeginger, The P-versus-NP page, http://www.win.tue.nl/~gwoegi/P-versus-NP.htm