Facet identification for the symmetric traveling salesman polytope (Q918865)

The paper summarizes a variety of procedures which constitute the core of a polytopal cutting plane algorithm to solve the symmetric traveling salesman problem by a sequence of linear relaxations. The basic problem is to identify facet inducing inequalities ``efficiently''. In the paper four classes of well known faces of the symmetric traveling salesman polytope are analyzed: (a) subtour elimination inequalities, (b) 2- matching inequalities, (c) comb inequalities, (d) clique tree inequalities. The authors give a polynomial time and exact procedure which identifies subtour elimination inequalities which are violated by the current solution. The basis for this procedure is the detection of the minimum capacity cut or a shrinkable edge. Reduction techniques for 2-matching constraints are introduced and yield a basis for an efficient algorithm for the identification of violated 2-matching constraints. The most difficult part is the identification of comb inequalities which are analyzed in detail. The paper concludes with the identification procedure for basic clique tree inequalities, outlines the identification algorithm in total and gives some hints to a lot of experimental results which are already published elsewhere.