期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 246, 期 2, 页码 392-399出版社
ELSEVIER
DOI: 10.1016/j.ejor.2015.05.001
关键词
Combinatorial optimization; Branch-and-cut; K-rooted mini-max spanning forest problem; Optimality cuts
资金
- CNPq [471464/2013-9, 305423/2012-6, 477863/2010-8, 483.243/2010-8, 304793/2011-6, 307026/2013-2]
- FAPEMIG [PPM-VII-00164-13, PRONEX APQ-01201-09]
- FAPERJ [E26-110.552/2010]
Let G = (V, E) be an undirected graph with costs associated with its edges and K pre-specified root vertices. The K-rooted mini-max spanning forest problem asks for a spanning forest of G defined by exactly K mutually disjoint trees. Each tree must contain a different root vertex and the cost of the most expensive tree must be minimum. This paper introduces a Branch-and-cut algorithm for the problem. It involves a multi-start Linear Programming heuristic and the separation of some new optimality cuts. Extensive computational tests indicate that the new algorithm significantly improves on the results available in the literature. Improvements being reflected by lower CPU times, smaller enumeration trees, and optimality certificates for previously unattainable K = 2 instances with as many as 200 vertices. Furthermore, for the first time, instances of the problem with K E (3,4) are solved to proven optimality. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据