Consider a set of nodes, each with an associated profit, and a set of arcs, each with an associated length. The objective of the orienteering problem is to find the path beginning at a specified origin and terminating at a specified destination that maximizes total profit subject to: (1) a constraint on the length of the path; and (2) the condition that no node is visited more than once. The problem may be formulated as a 0-1 integer program, and its has been shown to be NP-hard. Prior research has focused on heuristics that obtain lower bounds on the optimal objective function value. Some recent research proposed a branch-and-bound algorithm that solves a linear programming (LP) relaxation of the 0-1 model at each node and obtains an optimal orienteering path. The present research is concerned with tightening the LP relaxation by adding constraints and valid inequalities. The authors propose a procedure to obtain upper bounds by solving three successive linear programs. They test the present procedure on datasets in existing literature and demonstrate that the average deviation between the upper bounds and the best known lower bounds (feasible solutions) is less than five percent. The quality of upper bound obtained is significantly enhanced over the bound obtained from solving the basic LP relaxation.
