Model Persoalan Minimum Spanning Tree Diameter Terbatas

Abstract

The bounded diameter minimum spanning tree problem is a combinatorial op- timization problem appearing in applications such as wire-based communication network design when quality of service is of concern, in ad-hoc wireless networks, and also in the areas of data compression. Prior exact approaches for the bounded diameter minimum spanning tree problem problem mostly rely on network flow- based mixed integer linear programming. This research presents a new, compact 0-1 integer linear programming model, which is further strengthened by dynamical- ly adding violated connection and cycle elimination constraints within a branch- and-cut model. This will be done not just in the classical sense, for example by heuristically determining a good starting solution for an exact algorithm, but also by running different algorithms in parallel and letting them exchange information relevant for the optimization in order to benefit from synergy.