An Exact Algorithm with Tight Lower Bounds for the Capacitated Minimum Spanning Tree Problem

作者：Han Jun^*; Li Zhaoguo; Ge Sheng; Lei Ming

来源：Chinese Journal of Electronics, 2008, 17(4): 640-645.

• Lower bound
• Branch and bound
• Penalty cost

A solution method using branch and bound technique for the CMST problem is introduced in this paper. Techniques for finding tighter lower bounds are emphasized. On the basis of a constraint relaxed MST bound, a penalty cost is added to acquire tighter bound. The correctness of the proposed bound is proved and the improvement of the efficiency coursed by the bound is demonstrated by the computational tests. A further tighter bound is also proposed considering the size of disjoint groups when establishing the penalties. Test results on benchmark problem instances are presented.

• 出版日期2008-10
• 单位北京航空航天大学