#### A Hop and Degree Constrained Min-Sum Arborescence Problem

The hop and degree constrained hop-constrained arborescence problem consists of scheduling the installation of links in a network so as to connect a set of terminal nodes *N* = {2,3,......*n*} to a central node with minimal present value of expenditure such that: each terminal node *j* has exactly one entering link; for each terminal node *j*, a unique path from the central node to *j* exists; for each terminal node *j* the number of links between the central node and node *j* is limited to a predefined number *h*; and the number of links originating from for each terminal node *j *is limited to a predefined number *d*. Such problems are very difficult problem to solve optimally. Usually heuristic methods are used to find a good solution to such difficult problems. However, these heuristics do not guarantee the quality of the solution. In such cases, it would be beneficial to have some estimate of the quality of the solution given by the heuristic method. This researcher presents a Lagrangian based method to find a lower bound of the optimal solution. This lower bound can be used to estimate the quality of solution given by any heuristic method by finding the gap between the lower bound and the solution value of the heuristic method.

Return to this PI's main page.