  We present an O(n^6 ) linear programming model for the traveling salesman
(TSP) and quadratic assignment (QAP) problems. The basic model is developed
within the framework of the TSP. It does not involve the city-to-city
variables-based, traditional TSP polytope referred to in the literature as "the
TSP polytope." We do not model explicit Hamiltonian cycles of the cities.
Instead, we use a time-dependent abstraction of TSP tours and develop a direct
extended formulation of the linear assignment problem (LAP) polytope. The model
is exact in the sense that it has integral extreme points which are in
one-to-one correspondence with TSP tours. It can be solved optimally using any
linear programming (LP) solver, hence offering a new (incidental) proof of the
equality of the computational complexity classes "P" and "NP." The extensions
of the model to the time-dependent traveling salesman problem (TDTSP) as well
as the quadratic assignment problem (QAP) are straightforward. The reasons for
the non-applicability of existing negative extended formulations results for
"the TSP polytope" to the model in this paper as well as our software
implementation and the computational experimentation we conducted are briefly
discussed.
