Algorithmic Study Of Optimization Problems In Reliability Networks

While advanced technologies have raised the world to an unprecedented level of productivity, affluence, and health, our society today becomes more delicate and vulnerable due to the increasing dependence on modern technological systems that often require complicated operations and sophisticated management. From any respect, systems reliability is a crucial measure to be considered in systems operation and risk management. So there is a practical significance to develop efficient algorithms for reliability maximization and cost minimization problems arising in network systems. It is well known that systems reliability can be improved by adopting high reliability components. Improving reliability of a single component, however, is often restricted to technological bottleneck and may be very expensive. Therefore, optimal redundancy plays an important part in designing high reliability systems.In this thesis, we first consider the constrained redundancy optimization problem in series systems. The goal of the problem is to allocate an optimal redundancy assignment so as to maximize the overall system reliability under certain limited resource constraints. The problem can be formulated as following nonlinear integer programming problems:A closely related problem to (P₁) is the cost minimization in reliability systems. The problem is to minimize the cost of a series-parallel system under a minimum overall reliability requirement. The problem can be modelled as: In Chapter 3 we propose a new exact method for solving problem (P₁) and (P₂). The method is based on the Lagrangian dual search and a special partition technique. Due to the separability of the reliability optimization formulations, Lagrangian bounds of the problem can be computed efficiently by dual search procedures. To reduce the duality gap, we partition the integer domain into integer subboxes by using the monotonicity of the reliability function and constraint functions. A special optimality criterion for series-parallel reliability optimization problems is adopted to improve the performance of the algorithm. One of prominent findings from our computational experiment is that the outer approximation method significantly outperforms the subgradient method as a dual search procedures for problem (P₁) with multiple constraints.In some models of reliability networks, apart from an overall resource constraint, there are additional local (group) constraints for subsystems. The group constraints are often presented in system design when resource restrictions only involve the components in some subsystems, without affecting other parts of the overall system. The problem can be formulated as the following nonlinear integer programming problem:We present in Chapter 3 an efficient method for solving (P₃). The method exploits the special structures of global constraint and local constraints. We use Dantzig-Wolfe decomposition scheme to obtain the upper bound of the problem. The relaxation subproblems are subject to a single group constraint and can be solved efficiently by dynamic programming. A special domain partition technique is adopted to reduce the duality gap successively.In Chapter 4, we consider the constrained reliability problem in a series system with multiple component choices. The problem is to allocate an optimal redundancy assignment under multiple resource constraints. The problem can be formulated as a nonlinear integer programming problem:The cost minimization problem related to (P4) isSince r_ij's can be different in the i-th subsystem, the reliability function R(x) is in general a nonseparable function. This makes it a great challenge to design efficient solution methods for (P₄) and (P₅).An exact algorithm is proposed for (P₄) in Chapter 4. To overcome the nonseparability of the reliability function, we first approximate a reformulation of the nonseparable problem by a separable form via certain linear approximation. The resulting separable nonlinear integer programming problem is used to compute upper bounds by Lagrangian relaxation and dual search. The partition scheme is used to reduce the duality gap in a branch-and-bound process, thus ensuring the convergence of the algorithm. The performance of the algorithm is also improved by certain heuristics.In Chapter 5, we propose a new exact method for solving problem (P₅). Similar to (P₄), the method for (P₅) utilizes the linear approximation and Lagrangian bound. An alternative linear approximation of R(x) is derived and the resulting separable integer program is then solved by 0-1 linearization method.Computational results are reported in Chapter 6 to show the efficiency of the proposed methods in this thesis. Comparison numerical results with other methods are also reported. Finally, we conclude the thesis in Chapter 7 by sum marizing the main results and discussing some possible future research directions.