The probabilistic traveling salesman problem (PTSP) is defined on a graph G=(V,E), where V is the vertex set and E is the edge set. Each vertex vi has a probability pi of being present. With each edge (vi,vj) is associated a distance or cost cij. In a first stage, an a priori Hamiltonian tour on G is designed. The list of present vertices is then revealed. In a second stage, the a priori tour is followed by skipping the absent vertices. The PTSP consists of determining a first-stage solution that minimizes the expected cost of the second-stage tour. The problem is formulated as an integer linear stochastic program, and solved by means of a branch-and-cut approach which relaxes some of the constraints and uses lower bounding functionals on the objective function. Problems involving up to 50 vertices are solved to optimality.
