A network-based relaxation approach for selecting optimal bridge replacement or rehabilitation strategies

A model and solution methodology are developed for determining the most cost-effective rehabilitation and replacement activities for each bridge in a large-scale Bridge Management System along an extended planning horizon. The objective of the optimization model, formulated as a multi-dimensional 0-1 knapsack problem with multiple-choice constraints, is to maximize the total effectiveness of bridge activities in the set of selected projects. The solution approach is based on a specialized branch-and-bound procedure with embedded Lagrangean relaxation. Subgradient optimization is used to solve the relaxed problem along with a set of valid inequalities obtained from a generalized network representation of the problem with the purpose of improving the bounds. Computational results indicate that large-scale problems considering one thousand bridges requiring several thousand bridge projects can be solved within 0.05 percent of the upper bounds on the objective function value in an average computer time of 49 minutes using a personal computer.