A Reach and Bound algorithm for acyclic dynamic-programming networks

Abstract

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 [epsiv]-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. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008