Reliability-redundancy allocation problem in multi-state flow network: Minimal cut-based approximation scheme

Reliability-redundancy allocation problem (RRAP), a challenging reliability optimization problem, aims to optimize the redundancy level and the component reliability simultaneously for each stage (i.e. subsystem) of the system. The RRAP was mainly studied under binary-state setting on different redundancy strategies, methodologies, and multi-objective formulations. However, the methods are all meta-heuristic algorithms, and no studies focused on RRAP in multi-state flow network (MFN) systems. In this paper, we study the RRAP in MFN considering the minimization of cost or the maximization of reliability under resource constraints. The MFN RRAP is a mixed-integer non-linear programming problem, which is NP-hard. We propose a minimal cut-based approximation scheme to transform it into an integer programming problem. The feasibility guarantee is analyzed to ensure that this approximation scheme can generate a feasible solution with a high probability. The posterior check is conducted to reduce the conservative theoretical sample size empirically. The numerical experiments on MFNs illustrate the tradeoff performance between the accuracy of solutions and the computational complexity, and the outperformance of our proposed method compared to a meta-heuristic algorithm.