A Reach and Bound algorithm for acyclic dynamic-programming networks

A Reach and Bound algorithm for acyclic dynamic-programming networks

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound, 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 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.

Reviews

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