  The Covering Salesman Problem (CSP) is a generalization of the Traveling
Salesman Problem in which the tour is not required to visit all vertices, as
long as all vertices are covered by the tour. The objective of CSP is to find a
minimum length Hamiltonian cycle over a subset of vertices that covers an
undirected graph. In this paper, valid inequalities from the generalized
traveling salesman problem are applied to the CSP in addition to new valid
inequalities that explore distinct aspects of the problem. A branch-and-cut
framework assembles exact and heuristic separation routines for integer and
fractional CSP solutions. Computational experiments show that the proposed
framework outperformed methodologies from literature with respect to optimality
gaps. Moreover, optimal solutions were proven for several previously unsolved
instances.
