The traveling salesman problem: A Linear programming formulation

Abstract

In this paper, we present a polynomial-sized linear programming formulation of the Traveling Salesman Problem (TSP). The proposed linear program is a network flow-based model. Numerical implementation issues and results are discussed. (The exposition and proofs are much more detailed in an edition which I wrote in collaboration with Dr. M.H. Karwan in 2012-2014 . That edition is available at http://users.business.uconn.edu/mdiaby/P=NPProofPapers/tspPaper.pdf)

10 pages; Published in "WSEAS Transactions on Mathematics." Constraints added to rectify minor oversight in proof of proposition 2 (Theoretical development is same). Hofman's claim of a "counter-example" (arXiv cs/0610125 and cs/0611008) is invalid: violates constraints 2.11-2.15

Cited by in corpus (7)

• Postulate-based proof of the P != NP hypothesis
• A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
• On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims
• Linear Programming Formulation of the Boolean Satisfiability Problem
• A O(n^8) X O(n^7) Linear Programming Model of the Traveling Salesman Problem
• A O(n^8) X O(n^7) Linear Programming Model of the Quadratic Assignment Problem
• On Limits to the Scope of the Extended Formulations "Barriers"