Orienteering Problem
In the Orienteering Problem (OP) we are given an undirected graph
with edge weights and node prizes. The problem calls for a simple
cycle whose total edge weight does not exceed a given threshold,
while visiting a subset of nodes with maximum total prize.
This {\em NP}-hard problem arises in routing and scheduling applications.
We describe a branch-and-cut algorithm for finding an optimal OP
solution. The algorithm is based on several families of valid inequalities.
We also introduce a family of cuts which can cut off the optimal OP
solution, called conditional cuts, and propose an effective way to use
them within the overall branch-and-cut framework.
Exact and heuristic separation algorithms are described,
as well as heuristic procedures to produce near-optimal OP solutions.
An extensive computational analysis on several classes of both real-world
and random instances is reported. The algorithm proved to be able
to solve to optimality large-scale instances
involving up to 500 nodes,
within acceptable computing time.
This compares favourably with previous published methods.
My contributions with P. Toth and M. Fischetti are:
Solving the Orienteering Problem through Branch-and-Cut,
INFORMS Journal on Computing 10/2 (1998) 133-148.