The symmetric traveling salesman problem is one of the most famous and typical problems in combinatorial optimization. Being NP-complete, attempts for solving it to optimality mostly resort, one way or another, to tree search algorithms. The tree search algorithms mostly differ in their lower bounding, upper bounding, branching rules and variable fixing approaches. The 1–tree problem in association with Lagrangean relaxation is among the most widely used lower bounding strategies reported in branch and bound techniques. This work first reviews the branch and bound based solution approaches for the traveling salesman problem. Then the effectiveness of the existing branching strategies is empirically evaluated against each other. The data correction algorithm (DCA), is a recursive branch and bound type algorithm in which the data of the given problem instance is ‘corrected’ at each branching in such a way that the new instance is polynomially solvable. The thesis also investigates the applicability of the data correction algorithm to the symmetric traveling salesman problem by using 1-tree matrices.

Keywords: Traveling Salesman Problem, Branch and Bound, Data Correction Algorithm.