  The Team Orienteering Problem (TOP) is an NP-hard routing problem in which a
fleet of identical vehicles aims at collecting rewards (prizes) available at
given locations, while satisfying restrictions on the travel times. In TOP,
each location can be visited by at most one vehicle, and the goal is to
maximize the total sum of rewards collected by the vehicles within a given time
limit. In this paper, we propose a generalization of TOP, namely the Steiner
Team Orienteering Problem (STOP). In STOP, we provide, additionally, a subset
of mandatory locations. In this sense, STOP also aims at maximizing the total
sum of rewards collected within the time limit, but, now, every mandatory
location must be visited. In this work, we propose a new commodity-based
formulation for STOP and use it within a cutting-plane scheme. The algorithm
benefits from the compactness and strength of the proposed formulation and
works by separating three families of valid inequalities, which consist of some
general connectivity constraints, classical lifted cover inequalities based on
dual bounds and a class of conflict cuts. To our knowledge, the last class of
inequalities is also introduced in this work. A state-of-the-art branch-and-cut
algorithm from the literature of TOP is adapted to STOP and used as baseline to
evaluate the performance of the cutting-plane. Extensive computational
experiments show the competitiveness of the new algorithm while solving several
STOP and TOP instances. In particular, it is able to solve, in total, 14 more
TOP instances than any other previous exact algorithm and finds eight new
optimality certificates. With respect to the new STOP instances introduced in
this work, our algorithm solves 30 more instances than the baseline.
