Column generation approach for the traveling salesman problem

We present a new approach, columnwise formulation and column generation, for solving structured combinatorial optimization problems. Instead of defining classes of valid inequalities as in polyhedral combinatorics, we systematically reformulate the problem into a linear program with an exponential number of columns which we solve by column generation. Like polyhedral combinatorics and Lagrangian relaxation, our approach is for general combinatorial optimization problems. Recently, the branch-and-price method which combines branch-and-bound with primal column generation scheme is also developed. A new column generation method, the primal-dual column generation procedure, based on the primal-dual simplex method is developed. Incorporating this procedure into the branch-and-bound framework, we develop a branch-and-generate method to find an exact solution for the problem. The traveling salesman problem (TSP) is used to test the newly developed branch-and-generate method. First, we formulate the TSP as a complementary columnwise formulation in which each column represents either a 1-tree or a 2-matching. Then, we use the primal-dual column generation procedure to solve the problem and obtain a lower bound that is equivalent to that from the intersection of 1-tree and 2-matching polytopes. A crucial advantage of the branch-and-generate method is that information obtained at each branch-and-bound node, i.e., the column representation, can be carried over to its successor nodes. Computational results indicate that our method is viable and the number of nodes in the branch-and-bound tree for a moderate size problem is well under control