On a linear programming-combinatorial approach to the traveling salesman problem
A more detailed description of the linear-programming approach in solving the traveling salesman problem that that presented in P-510. The present study considers the example discussed by L. L. Barachet ("Graphic Solution of the Traveling Salesman Problem," published in Operations Research, Vol. 5, 1957), in which he describes a procedure of successively improving a solution by using certain necessary conditions for optimality and indicates that there is no guarantee that the final tour obtained by his approach is optimal. In addition, this paper starts with Barachet's initial tour, improves it, and gives a proof that his final solution is indeed optimal.