Interaction Theory New Paradigm For Solving Traveling Salesman Problem (TSP)

Anang Z. Gani

Abstract
This paper presents a new paradigm for solving the Travelling Salesman Problem (TSP). TSPis known as an NP-complete problem in combinatorial optimization, whichis a problem related to complexity theory. If the TSP can be solved using an algorithm in polynomial time, this will prove that NP problem can be solved in polynomial time (P = NP). 

In early development of Linear Programming, scientists were using and expecting Linear Programming to solve TSP. But there were difficulties in the process, since the number of iterations increases very rapidly along with the increase in the size of the problem. Hence, huge spaces of computer resources are required. Subsequently, Linear Programming and other exact methods have been improved. In addition to that, many heuristic methods have been widely developed to solve the TSP. The development of computer technology is also contributing in the attempt to solve the large-scale Traveling Salesman Problem. However,it still seems difficult to solve the iteration problem. Not even the progress of computer technology can meet the needs of the computer space required to perform the iterations. Therefore, it is commonly believed that there is no efficient and effective algorithm that can solve the TSP in polynomial time. 

The Interaction Theory has been developed since 1966. It is a new approach to solve TSP,in that it is different from the existing philosophies in the field of Mathematic, Computer Science and Operations Research. A new and simple formula is introduced, including introducing an "interaction coefficient" of the TSP: ci,j= xi,j2/(Xi. .X.j), which is a breakthrough for a TSP algorithm.The process of finding a solution does not require calculation of all paths of possible routes. It is a very big saving in time and storage space. 

The Interaction Theory is a new concept that gives the exact result of TSP with polynomial time (P=NP).It is also very effective for solving manually, not only the simple problems, but also complicated and large scale problems. Occasionally, it provides more than one optimum solution. Moreover, The Interaction Theory solves the maximization and minimization problem not only for the Symmetric Traveling Salesman Problem (STSP) easily, but it also can solve quickly and easily the Assymetric Traveling Salesman Problem (ATSP).

(Keywords: Graph; NP-Problem; Combinatorial Optimization; Traveling Salesman Problem; Complexity Theory; Integer Programming; Linear Programming; Interaction Theory).