Orienteering Problem
The Cycle Problem (CP) is related with the well-known
Travelling Salesman Problem (TSP): instead of looking for
a min-cost cycle visiting each city ``exactly'' once, CP looks for
a min-cost cycle visiting each city ``at most'' once.
For general edge costs, CP is an NP-hard problem,
comparing as relaxation of several important combinatorial problems.
From a theoretical point of view, CP presents an associated
polytope easily described as the convex hull of the simple cycles,
but not too many facets are known. In this work we propose a
polyhedral study of CP on un-directed graphs, showing that
the linear inequalities in the classical ILP model are facets,
extending the comb inequalities from the TSP to CP, and
proposing a new lifting procedure for obtaining facets for CP
from facets for TSP.
My contributions are:
On the Cycle Polytope of a Undirected Graph,
University of La Laguna Tenerife (april 1994)