Article ID: | iaor200969339 |
Country: | United States |
Volume: | 52 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 7 |
Publication Date: | Aug 2008 |
Journal: | Networks |
Authors: | Smith Robert L, Bailey Matthew D, Alden Jeffrey M |
Keywords: | programming: branch and bound, networks |
Node pruning is a commonly used technique for solution acceleration in a dynamic-programming network. In pruning, nodes are adaptively removed from the dynamic programming network when they are determined not to lie on an optimal path. We introduce an e-pruning condition that extends pruning to include a possible error in the pruning step. This results in a greater reduction of the computation time; however, as a result of the inclusion of this error, the solution can be suboptimal or possibly infeasible. This condition requires the ability to compare the costs of an optimal path from a node to a terminal node. Therefore, we focus on the class of acyclic dynamic programming networks with monotonically decreasing optimal costs-to-go. We provide an easily implementable algorithm, Reach and Bound, which maintains feasibility and bounds the solution's error. We conclude by illustrating the applicability of Reach and Bound on a problem of single location capacity expansion.