In this paper, an exact algorithm was proposed for optimal redundancy in a series system with multiple component choices. A reformulation of the nonseparable reliability function was approximated by a separable integer programming problem. The resulting separable nonlinear integer programming problem is used to compute upper bounds by Lagrangian relaxation and dual search. A special partition scheme was derived to reduce the duality gap in a branch-and-bound process, thus ensure the convergence of the algorithm.Computational results show that the algorithm is efficient for solving this class of reliability optimization problems.