Title :
Heuristic Cut Separation in a Branch&Cut Approach for the Bounded Diameter Minimum Spanning Tree Problem
Author :
Gruber, Martin ; Raidl, Günther R.
Author_Institution :
Inst. of Comput. Graphics & Algorithms, Vienna Univ. of Technol., Vienna
fDate :
July 28 2008-Aug. 1 2008
Abstract :
The bounded diameter minimum spanning tree problem is an NP-hard combinatorial optimization problem arising for example in network design when quality of service is of concern. We solve a strong integer linear programming formulation based on so-called jump cuts by a novel branch&cut algorithm, using various heuristics including tabu search to solve the separation problem.
Keywords :
computational complexity; integer programming; linear programming; tree searching; trees (mathematics); NP-hard combinatorial optimization problem; bounded diameter minimum spanning tree problem; branch&cut approach; heuristic cut separation problem; integer linear programming formulation; jump cuts; tabu search; Algorithm design and analysis; Application software; Computer graphics; Costs; Design optimization; IP networks; Integer linear programming; Quality of service; Tree graphs; Web and internet services; bounded diameter minimum spanning tree; branch-and-cut; local search; tabu search;
Conference_Titel :
Applications and the Internet, 2008. SAINT 2008. International Symposium on
Conference_Location :
Turku
Print_ISBN :
978-0-7695-3297-4
DOI :
10.1109/SAINT.2008.68
