# zbMATH — the first resource for mathematics

A priori optimization of the probabilistic traveling salesman problem. (English) Zbl 0810.90124
Summary: 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 $$v_ i$$ has a probability $$p_ i$$ of being present. With each edge $$(v_ i,v_ j)$$ is associated a distance or cost $$c_{ij}$$. 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.

##### MSC:
 90C35 Programming involving graphs or networks 90C15 Stochastic programming 90C10 Integer programming
Full Text: