A branch and bound algorithm for solving a capacitated subtree of a tree problem in local access telecommunication networks

A branch and bound algorithm for solving a capacitated subtree of a tree problem in local access telecommunication networks

0.00 Avg rating0 Votes
Article ID: iaor19983000
Country: South Korea
Volume: 22
Issue: 3
Start Page Number: 81
End Page Number: 98
Publication Date: Sep 1997
Journal: Journal of the Korean ORMS Society
Authors: ,
Keywords: programming: integer, networks: path, programming: dynamic
Abstract:

Given a rooted tree T with node profits and node demands, the capacitated subtree of a tree problem (CSTP) consists of finding a rooted subtree of maximum profit, subject to having total demand no larger than the given capacity H. We first define the so-called critical item for CSTP and find an upper bound on the optimal value of CSTP in O(n2) time, where n is the number of nodes in T. We then present our branch and bound algorithm for solving CSTP and illustrate the algorithm by using an example. Finally, we implement our branch-and-bound algorithm and compare the computational results with those for both CPLEX and a dynamic programming algorithm. The comparison shows that our branch and bound algorithm performs much better than both CPLEX and the dynamic programming algorithm, where n and H are in the range of [50, 500] and [5000, 10000], respectively.

Reviews

Required fields are marked *. Your email address will not be published.