Network programming technique in the symmetric traveling salesman problem

A dual problem is formulated where the constraints are split into 2 groups with corresponding division of arcs into 2 parts and solution of the resulting 2 evaluation problems. The sum of the objective functions of optimal solutions to the evaluation problems gives the lower bound for the original problem. The solution of the evaluation task is reduced to the design of the shortest $i$-trees. A new method for building the lower bounds for evaluation problems underlain by the shortest-distance tree design is proposed. The paper shows that the design of $i$-trees and the shortest-distance tree for the original distance matrix would not deliver an optimal solution to the dual problem.