A hybrid ‘dynamic programming/depth-first search’ algorithm, with an application to redundancy allocation

A hybrid ‘dynamic programming/depth-first search’ algorithm has been developed to solve non-linear integer programming problems arising in the reliability optimization of redundancy allocation. Initially, the technique solves the knapsack relaxation of the original mathematical programming problem using dynamic programming. Then, all solutions in some range of the relaxation problem are obtained via an enumerative depth-first search technique. The solutions are ranked and the optimal solution is given by the best one that satisfies the remaining constraints of the given problem. Computational complexity of the algorithm is also discussed. The salient features of our hybrid algorithm are its simplicity and ease of programming. Our algorithm also has an advantage over the traditional Lagrangian and surrogate dual approaches. It does not have to deal with the issue of ‘duality gap’ as in classical dual approaches, which is responsible for the failure to identify optimal solutions to the primal integer optimization problems. Of most importance, it guarantees to succeed in identifying an optimal solution.