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 φ(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 φ(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 φ(t, y).