TAILIEUCHUNG - 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}@ Nelson MACULAN COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil maculan@ 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}

• Toán học
• Fundamental cycle
• Cycle basis
• IP formulation
• Tree growing heuristic
• Alternative heuristics
• Accounting cycle
• Completing the accounting cycle
• Classified balance sheet
• Accounting principles
• Fundamental accounting principles
• Lecture Fundamental accounting principles
• Fundamental accounting
• Business transactions
• Adjusting accounts
• Completing the accounting cycle operations
• Financial accounting
• Fundamental financial accounting
• Lecture Fundamental financial accounting concepts
• Financial statement
• Accounting for accruals
• Merchandise operations
• Accounting for merchandise operations
• Merchandising activities