Đang chuẩn bị liên kết để tải về tài liệu:
Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases

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 relaxations. | Yugoslav Journal of Operations Research 15 (2005), Number 1, 15-24 MATHEMATICAL MODELS AND A CONSTRUCTIVE HEURISTIC FOR FINDING MINIMUM FUNDAMENTAL CYCLE BASES Leo LIBERTI, Edoardo AMALDI, Francesco MAFFIOLI DEI, Politecnico di Milano, Milano, Italy {liberti,amaldi,maffioli}@elet.polimi.it Nelson MACULAN COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil maculan@cos.ufrj.br Presented at XXX Yugoslav Simposium on Operations Research Received: January 2004 / Accepted: February 2005 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 relaxations. 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. Keywords: Fundamental cycle, cycle basis, IP formulation, tree-growing heuristic. 1. INTRODUCTION Let G = (V , E ) be a simple, undirected, biconnected graph with n nodes and m edges, where each edge e ∈ E is assigned a weight we ∈ R . A cycle is a subset C of E such that every node of V is incident with an even number of edges in C. Since an elementary cycle is a connected cycle such that at most two edges are incident to any node, cycles can be viewed as the (possibly empty) union of edge-disjoint elementary cycles. If cycles are considered as edge-incidence binary vectors in {0,1}| E | , it is well- 16 L. Liberti et al. / Mathematical Models and a Constructive Heuristic known that the cycles of a graph form a vector space over GF (2) . A set of cycles is a cycle basis if it is a basis in this cycle vector space associated to G. The cost of a cycle