zbMATH — the first resource for mathematics

A branch-and-cut algorithm for the undirected selective traveling salesman problem. (English) Zbl 1002.90044
Summary: 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 tour of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of valid 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.

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
Full Text: DOI