Branch-and-Cut Algorithms And A Branch-and-Cut Algorithm For Blocked TSP

Branch-and-cut methods are very successful techniques for solving a wide variety of integer programming problems, and they can provide a guarantee optimality. Branch-and-cut methods can solve many combinatorial optimization problems, especially large scale problems, for instance, traveling salesman problem(TSP).In this paper, we analyze the methods from two aspects, cutting planes and branching on the basis of branch-and-cut algorithms. Moreover, considering a class of special TSP. The cities in this kind of TSP can be divided several blocks. Then, we express the special TSP with 0-1 mixed integer linear programming(MILP). After that, we use branch-and-cut methods to it and discuss it from cutting planes and branching. The way of blocking the TSP can reduce the scale, so it is a good way. Solving it with branch-and-cut methods, we can see the advantage of the methods.