Nonlinear resolving functions for the travelling salesman problem

We propose two approaches to finding lower bounds in the traveling salesman problem (TSP). The first approach, based on a linear specification of the resolving function $\varphi(t,y)$, uses a two-index TSP model in its solution. This model has many applications. The second approach, based on a nonlinear specification of the resolving function $\varphi(t,y)$, uses a single-index TSP model. This model is original and lets us significantly reduce the branching procedure in the branch-and-bound method for exact TSP solution. One cannot use the two-index TSP model here due to the nonlinear specification of the resolving function $\varphi(t,y)$.

Presented by the member of Editorial Board: A. A. Lazarev