1. INTRODUCTION
Reliability refers to the ability of a system to provide the required functionality for a specified period in a given environment. For example, designing a weapon system should provide high reliability, and it is critical to achieve target reliability by considering available resources such as volume, budget, weight. Problem of designing a system structure to achieve the desired reliability is called a reliability optimization problem (ROP). Since ROP arises in many practical applications, numerous extended and modified versions of the problems are studied (several review papers can be found in (Kuo and Wan, 2007;Soltani, 2014;Twum and Aspinwall, 2013). Also, recent similar studies can be found in (Peiravi et al., 2019;Ardakan et al., 2015;Feizabadi and Jahromi, 2017;Gholinezhad and Hamadani, 2017;Jahromi and Feizabadi, 2017;Ardakan and Hamadani, 2014;Shekhar et al., 2017;Zoulfaghari et al., 2015). Although not directly related to this study, some recent studies with similar purposes are found in (Aslam et al., 2015, 2018;Sindhu et al., 2019).
In this paper, we deal with one of ROP, more specifically, where the (1) placement of components is a series structure, (2) there are alternatives for a component that can be selected, (3) achieving a target reliability is a requirement, and (4) objective is a cost minimization (throughout this paper, this problem will be referred to as a reliability optimization problemcost minimization (ROPC_{min})).
When each component of the system is connected in series, the reliability of the system can be calculated as $\prod}_{i=1}^{n}{r}_{i$ (system is composed of n number of components and reliability of component i is r_{i}), which is the most common type of system structure that can be observed in a real world. We also assume that, if we can pay a higher cost for a certain component, a replaceable component with higher reliability can be purchased (that is, if c_{i} > c_{j}, then r_{i} > r_{j}). In summary, selectable alternatives exist in ROPC_{min}.
Many of the existing studies have been performed on, where the constraint is a cost restriction and the objective is reliability maximization (throughout this paper, this problem will be referred to as a reliability optimization problemreliability maximization (ROPR_{max})). To avoid confusion of understanding, comparison between the ROPC_{min} and ROPR_{max} in terms of objective and constraints is summarized in Table 1.
Previous studies on ROPR_{max} can be classified as developing an optimization algorithm (which guarantees to find an optimal solution) and a heuristic algorithm (which can probably find a good solution). Since ROPR_{max} can be converted to a wellknown multiplechoice knapsack problem (MCKP) (Sung and Cho, 2000), many optimization approaches can be found in (Ahmadizar and Soltanpanah, 2011;Dyer et al., 1995;Nauss, 1978;Sinha and Zoltners, 1979). Also, studies that provide heuristic algorithms can be found in (Kim et al., 2004, 2008; Coit and Smith, 1996;Nahas and Nourelfath, 2005;Truong et al., 2013).
The most similar study to this paper was conducted in (Elegbede et al., 2003). The similarities are, an objective is a cost minimization of the system, the restriction is satisfying the target reliability, and optimal methods are discussed. However, subject systems are different from parallelseries system to a series system with selectable alternatives and objectives are dissimilar from allocation of reliability and redundancy to select alternatives for components.
In (Moon et al., 2014) and (Na, 2017), the authors claimed that many defense R&D projects turn out to be exceeding the planned budget significantly. Therefore, minimizing the cost satisfying the target reliability is an urgent issue in the Republic of Korea. The author in (Na, 2017) claimed that ROPC_{min} is solved with Genetic Algorithm and Simulated Annealing in total life cycle management of weapon systems, and the solution is used in validation of military R&D target RAM (reliability, availability, maintainability) values.
However, to the best of authors’ knowledge, no optimal algorithm for ROPC_{min} can be found, and this research devotes to developing an optimal algorithm for ROPC_{min}.
This paper is composed as follows. In section 2, we present a binary integer programming model for the ROPC_{min}. In section 3, we present optimization and heuristic algorithm for the ROPC_{min}. The optimal algorithm solves the modified ROPR_{max} several times until the optimal solution is obtained. The heuristic provides a bound for the optimal algorithm. In section 4, we implemented the algorithms and showed the performances in terms of the consumed CPU time to obtain the optimal solution. Some observations will also be discussed. Finally, section 5 summarizes the main contribution of this paper and presents some future research directions.
2. MATHEMATICAL FORMULATION
In this section, we devise the ROPC_{min} in mathematical symbols and expressions. ROPC_{min} considered in this research assumes that n components are connected in series, as shown in Figure 1. The objective is minimizing the cost while satisfying the minimum requirement of system reliability.
To express the problem in a mathematical model, we define some symbols and decision variables as the following (in this research, we assume that if c_{i} > c_{j}, then r_{i} > r_{j}).
Now a mathematical formulation can be given below.
The objective function (1) means we want to minimize the sum of the costs of the selected alternatives, nonlinear constraints (2) indicate that the required minimum system reliability (R) needs to be satisfied by the selected components in series, constraints (3) explain that exactly one alternative is required to be selected for a component i among m_{i} alternatives, and lastly, constraints (4) denote the requirement of binary decision variables.
Since the constraint (2) is modeled as a nonlinear expression, it is known to be difficult to solve optimally. Therefore, new optimal method is required to be designed to address the problem.
3. OPTIMAL AND HEURISTIC ALGORITHMS
In this section, we propose an optimal and heuristic algorithm for ROPC_{min}, and the optimal algorithm uses the generated bound from heuristic.
3.1 Optimal Algorithm
Before we explain the optimal algorithm more in detail, we introduce a mathematical formulation for the ROPR_{max} where n components are connected in series and the objective is maximizing the system reliability under cost restriction. We define some additional symbols as the following.

R_{s}: Reliability of the system when the selected alternatives are connected in series

C: Maximum allowable cost for a system
Now the mathematical formulation for ROPR_{max} can be given below.
The objective function (5) means maximizing the system reliability of the selected alternatives, constraints (6) indicate the cost restriction, and constraints (7) explain exactly one alternative can be selected for each component. Last constraints (8) mean every x_{ij} variables take a value of zero or one.
Let the formulations of ROPC_{min} and ROPR_{max} as Min.C_{S} and Max.R_{S}, respectively. Many studies have been performed to solve Max.R_{S} optimally or approximately. Authors in (Sung and Cho, 2000) claimed to use transforming the nonlinear objective function into a linear one by taking the logarithm as follows.
Then, the transformed problem with the remaining constraints of Max.R_{S} equals a wellknown multiplechoice knapsack problem (MCKP). MCKP is defined as a binary knapsack problem with an addition of disjoint multiplechoice constraints (Sinha and Zoltners, 1979). Although MCKP is known to be NPcomplete (Ibaraki and et al., 1978), its linear relaxation by dropping the binary restriction can be solved very efficiently. Many O(n) algorithms ((Dyer et al., 1995;Pisinger, 1995;Zemel, 1984) for linear MCKP have been developed, and as stated in (Martello and Toth, 1990), the MCKP can be solved in $O({\displaystyle {\sum}_{i}{n}_{i}\overline{b}})$, where $\sum}_{i}{n}_{i$ and $\overline{b}$ are the total number of alternatives and $\prod}_{q}{b}_{q$, respectively.
Research in (Kim et al., 2008) suggested to use of simulated annealing and tabusearch metaheuristic algorithms for ROPR_{max}, and compared the performance of the algorithms with an optimal solution from the optimization software (ILOG CPLEX 9.1). As they indicated, optimization software obtain the optimal solution within a second, and acquired optimal solution much faster than the heuristic does in some cases. Since the heuristic cannot guarantee obtaining an optimal solution, if we can find an optimal solution within a reasonable amount of time, then it is better.
In this paper, we used the good property of ROPR_{max} to solve the ROPC_{min} (note again that, the main purpose of this research is solving the ROPC_{min} exactly). Since the ROPC_{min} is a nonlinear programming formulation, we designed an optimal method with ROPR_{max} instead of address ROPC_{min} directly. We first solve ROPR_{max} with a huge positive value of C and check whether obtained R_{S} is greater than or equal to R. If R_{S} is greater than or equal to R, then we decrease C to a certain amount and solve ROPR_{max} again. This procedure will be stopped when R_{S} is smaller than R. Detailed procedure can be summarized in pseudocode as follows.

Step 1. Solve ROPR_{max} with parameter C optimally.

Step 2. Calculate system reliability with the obtained solution.

Step 3. Solve ROPR_{max} optimally.

Step 4. Calculate system reliability with the obtained solution.

Output: Decision either the minimum requirement of system reliability cannot be achieved or optimal solution, which guaranties the minimum sum of cost
The optimal algorithm described above can be justified according to the following proposition.
Proposition. If an optimal solution exists in ROPC_{min}, the discussed algorithm for ROPC_{min} finds an optimal solution.
Proof. After we solve ROPR_{max} optimally, there can be two cases. The first case is calculated R_{S} from the solution is greater than R, and the second case is R_{S} is smaller than or equal to R. In the first case, since an optimal solution x* from ROPR_{max} forms a feasible solution to ROPC_{min}, we can obtain a better solution in terms of cost by reducing the value of R in ROPR_{max}. Since the lower value of C guarantees equal or lower value of R (this is true because if c_{i}>c_{j}, then r_{i}>r_{j}.), we can decrease C to a certain amount.
Also, in the second case, x* from ROPR_{max} cannot be a feasible solution to ROPC_{min}, and no other solution can form a feasible solution to ROPC_{min} for a given C (since obtained R_{S} is obtainable maximum reliability for a given C.).
Since our algorithm designed for ROPC_{min} starts from a large enough value of C, it finds an optimal solution x*, which generates minimum system cost as long as the problem has a feasible solution.
3.2 Heuristic Algorithm
As discussed in the previous subsection, since the number of iterations (number of ROPR_{max} solved) for ROPC_{min} depends on the initial value of C and △, obtaining exact values of C and △ affects the convergence speed of the optimal algorithm. To obtain an initial value of C, we used a simple greedy approach as follows. Note that, since the main purpose of this research is to develop an exact algorithm for ROPC_{min}, no extra effort for heuristic was given in this paper. We first select the most expensive alternative for each component and check whether the product of each reliability ($\prod}_{i=1}^{n}{r}_{i$) is greater than or equal to R. If not so, the required system reliability cannot be achieved. Otherwise, we replace the selected alternative with the next most expensive alternative and calculate the system cost again. This process will be continued until the obtained reliability is greater than or equal to the required R.

Step 1. Choose the most expensive alternatives for each component.

Step 2. Calculate system reliability with the selected components.

Step 3. Choose the most expensive alternative among unselected alternatives and calculate system reliability with the selected components.

Output: Decision either the minimum requirement of system reliability cannot be achieved or upper bound for the system cost
Also, for convenience, an initial value of △ was set as the minimum increment unit of c_{ij}. If we can find the proper value of △, it will decrease the run time of the algorithm. However, since our algorithm found an optimal solution in a reasonable amount of time for all cases, no extra effort was given in finding tighter values of △ and C.
4. COMPUTATIONAL RESULTS
In this section, the performance of the optimal algorithm for ROPC_{min} was reported. The algorithm was implemented in optimization software Xpress Ver. 7.9 (FICO, 2019). Note that, although we tried solving the mathematical formulation of ROPC_{min} using nonlinear optimization software such as Lingo (Lindo, 2019) or Excel, we failed to obtain any feasible solution. All experiments were run on an Intel Pentium Dual Core (2.20GHz) with 2 GB RAM, and the running time of the algorithm was given in seconds. All experimental data sets were taken and modified from previous research (Nahas and Nourelfath, 2005). A summary of the four data sets was given in Table 3 (For the illustrative purposes, only data set 4 is given in Table 4 and the other three data sets can be found in (Nahas and Nourelfath, 2005) ).
In this experiment, there exists one parameter represents the minimum requirement of system reliability. If the value of R is too low or too high, the computational result of ROPC_{min} can be estimated trivially. Therefore, the value of R is changed from 0.5 to 0.9 with an increment of 0.1.
Here, several symbols are used to represent the computational results. Opt. represents the optimal value (=minimum cost) acquired from the optimal algorithm, Heu. means the cost which is obtained from the greedy heuristic, and lastly, Inf. means no feasible solution can be found under the given value of R. Since heuristic is used to accelerate the convergence speed of an optimal algorithm, Time includes running CPU time of heuristic.
Computational results are given in Tables 5, 6, and 7 and the optimal solutions are obtained within a insignificant amount of time. Also, we calculated the correlation between the (Heu.  Opt.) and Time, and it was 0.97. Therefore, we can infer that if we want to reduce the running time of the optimal algorithm, obtaining the tighter (=smaller) value of Heu. can be helpful.
5. CONCLUSIONS AND FUTURE WORKS
In this research, we considered ROPC_{min} (reliability optimization problemcost minimization) when n components (alternatives exist for each component) are connected in series and the objective is minimizing the cost while satisfying the requirement of system reliability. Since the problem is modeled as a nonlinear expression, we proposed an optimal algorithm and its main idea is solving the multiplechoice knapsack problem continuously until the optimal solution is obtained. Since the multiplechoice knapsack problem can be solved easily, computational results show that our optimal algorithm finds an optimal solution in a insignificant amount of time.
Also, we designed a simple greedy heuristic to accelerate the convergence speed of an optimal algorithm, and the heuristic provides the bound for the system cost. As discussed, convergence speed to an optimal solution to the problem depends on the gap between the bound from the heuristic and the objective function value from the optimal algorithm. Therefore, developing a better heuristic that can obtain a tight bound can be a good future research topic. Furthermore, the expansion of this research to develop optimal algorithms for other ROPs is required as a followup research.
Soochan Kim is a assistant professor in the department of mechanical & systems engineering at Korea Military Academy. His research interests are operations research and big data analysis.
Namsu Ahn is a associate professor in the department of mechanical & systems engineering at Korea Military Academy. His research interests are mathematical programming and quality management.