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

fYear

2008

fDate

July 28 2008-Aug. 1 2008

Firstpage

261

Lastpage

264

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Applications and the Internet, 2008. SAINT 2008. International Symposium on

Conference_Location

Turku

Print_ISBN

978-0-7695-3297-4

Type

conf

DOI

10.1109/SAINT.2008.68

Filename

4604586