A BRANCH-AND-CUT ALGORITHM FOR THE UNDIRECTED SELECTIVE TRAVELING SALESMAN PROBLEM

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a t our of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of va lid inequalities for the symmetric STSP and used them in a branch-and- cut algorithm. Depending on problem parameters, the proposed algorithm can solve instances involving up to 300 vertices. (C) 1998 John Wiley & Sons, Inc.