Efficient separation routines for the symmetric traveling salesman problem II: separating multi handle inequalities

This paper is the second in a series of two papers dedicated to the separation problem in the symmetric traveling salesman polytope. The first one gave the basic ideas behind the separation procedures and applied them to the separation of Comb inequalities. We here address the problem of separating inequalities which are all, in one way or another, a generalization of Comb inequalities. These are namely clique trees, path, and ladder inequalities. Computational results are reported for the solution of instances of the TSPLib using the branch and cut framework ABACUS.

Authors and Affiliations

1. Laboratoire Informatique et Distribution-IMAG, Institut National Polytechnique de Grenoble, e-mail: denis.naddef@imag.fr, , , , , , FR

   Denis Naddef

2. Institut für Informatik, Universität zu Köln, e-mail: Stefan.Thienel@sdm.de, , , , , , DE

   Stefan Thienel

Received: September 1999 / Accepted: August 2001¶Published online February 14, 2002

Reprints and permissions