The traveling salesman problem. Issues in theory

The first part of the paper surveys the theoretical results in solving the traveling salesman problem. Various (combinatorial, graph-theoretic, etc.) descriptions and linear and integer linear programming statements of the problem are provided. Actual problems reducible to the traveling salesman problem are described in detail. The computing complexity of the problem, the existence of a Hamiltonian cycle (loop), and numerous varieties of the problem are discussed.