Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases

Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases

0.00 Avg rating0 Votes
Article ID: iaor20053277
Country: Serbia
Volume: 15
Issue: 1
Start Page Number: 15
End Page Number: 24
Publication Date: Jan 2005
Journal: Yugoslav Journal of Operations Research
Authors: , , ,
Keywords: heuristics, programming: integer
Abstract:

The problem of finding a fundamental cycle basis with minimum total cost in a graph arises in many application fields. In this paper we present some integer linear programming formulations and we compare their performances, in terms of instance size, CPU time required for the solution, and quality of the associated lower bound derived by solving the corresponding continuous relaxation. Since only very small instances can be solved to optimality with these formulations and very large instances occur in a number of applications, we present a new constructive heuristic and compare it with alternative heuristics.

Reviews

Required fields are marked *. Your email address will not be published.