Login | Register

The Minimum Flow Cost Hamiltonian Tour Problem

Title:

The Minimum Flow Cost Hamiltonian Tour Problem

Ortiz, Camilo (2013) The Minimum Flow Cost Hamiltonian Tour Problem. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Ortiz_MSc_Fall2013.pdf - Accepted Version
662kB

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.

Divisions:Concordia University > Faculty of Arts and Science > Mathematics and Statistics
Item Type:Thesis (Masters)
Authors:Ortiz, Camilo
Institution:Concordia University
Degree Name:M. Sc.
Program:Mathematics
Date:24 July 2013
Thesis Supervisor(s):Contreras, Ivan and Gora, Pawel
ID Code:977521
Deposited By: Camilo Ortiz Astorquiza
Deposited On:26 Nov 2013 17:24
Last Modified:18 Jan 2018 17:44
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top