STRONG LINEAR-PROGRAMMING RELAXATIONS FOR THE ORIENTEERING PROBLEM

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 it 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 has 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. Our research is concerned with tightening the LP relaxation by adding constraints and valid inequalities. We propose a procedure to obtain upper bounds by solving three successive linear programs. We test our procedure on datasets in existing literature and demonstrate that the average deviation between our 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.