Abstract

In this thesis we introduce the minimum flow cost Hamiltonian tour problem(FCHT). Given a graph and positive flow between pairs of vertices, the FCHT consists of �finding a Hamiltonian cycle that minimizes the total cost for sending flows between pairs of vertices thorough the shortest path on the cycle. We prove that the FCHT belongs to the class of NP-hard problems and study the polyhedral structure of its set of feasible solutions. In particular, we present �five di�different MIP formulations which are theoretically and computationally compared. We also develop some approximate and exact solution procedures to solve the FCHT. We present a combinatorial bound and two heuristic procedures: a greedy deterministic method and a greedy randomized adaptive search procedure. Finally, a branch-and-cut algorithm is also proposed to solve the problem exactly.