به حداقل رساندن هزینه دقیق یک سیستم قابل اعتماد سری موازی با انتخاب جزء های متعدد با استفاده از روش جبری

The redundancy allocation problem is formulated minimizing the design cost for a series-parallel system with multiple component choices while ensuring a given system reliability level. The obtained model is a nonlinear integer programming problem with a nonlinear, nonseparable constraint. We propose a method based on the construction of a test set of an integer linear problem, which allows us to obtain an exact solution of the problem. It is compared to other approaches in the literature and standard nonlinear solvers.

System reliability is considered an important measure in the engineering design process. A series system is similar to a chain composed of links, each one representing a subsystem. The failure of one of these components means the failure of the whole system. In order to avoid this, it is usual to use redundant components in parallel to guarantee a certain level of reliability. These systems are called series-parallel systems. Determining the optimal number of components in each subsystem is the so-called reliability optimization problem. Two different approaches are usual: • maximize system reliability subject to system budget constraint or • minimize system cost subject to a required level of reliability. Both problems are nonlinear integer programming problems, and they are NP-hard [7]. There are very few papers looking for their exact solutions, due to the difficulty of the problems. Those works use essentially dynamic programming [22], branch and bound methods [13], or Lagrangian relaxation [17], among other techniques. On the contrary, in the literature there are many heuristics and metaheuristic algorithms, such as those based on genetic algorithms [8], tabu search [16] or ant colony optimization [3], among others. In this paper we study the exact solution of one of the versions of the problem that minimizes the cost function of the chosen design, subject to a nonlinear constraint which describes the reliability of the considered system. For a fixed subsystem, its inner components can be considered equal, as in [13], or different, as in [17] and [22]. If the components are equal, the reliability function is separable and convex, and the problem can be reduced to a linear knapsack problem [13]. In the case of multiple component choices, the reliability function is no longer separable. In [22], the solution is found using dynamic programming methods. That approach presents two stages. In the first one the problem is restricted to each subsystem, with a level of reliability. Under this assumption the reliability function is separable, and the optimization problem reduces to a knapsack problem. Those knapsack problems need discrete values to be solved, and the level of accuracy is determined by a constant L. So the exactness of solution is not guaranteed, a priori. The reliability levels of the subsystems are determined using some lower and upper bounds that also depend on the level of accuracy L, and a new dynamic programming process is needed. The solution method shown in [17] uses an algorithm based on Lagrangian relaxations over two linear relaxations of the original problem. The first relaxation consists of deleting the nonlinear reliability constraint, and adding certain linear constraints, one for each subsystem. The second relaxation assumes that the same type of component is going to be used in every subsystem, so that the problem reduces to one similar as in [13]. The algorithm of [17] is what their authors call a cut and partition scheme (a geometric branch and bound). The solution space is partitioned in boxes, which are divided and discarded under certain conditions. The cuts are built from the best bound feasible solution of the above mentioned Lagrangian relaxations. Such bounds allow to remove certain boxes depending on the improvement with respect to the current best point. We address the problem via a different approach based on Gröbner bases, which in this framework gives better computational results than other methods in the literature. As an introduction on this subject, we recommend the text books [2], [5] and [11]. Gröbner bases were applied to integer linear programming, for the first time, in [9]. Later, Tayur et al. [21] introduced a new application framework, which solves nonlinear integer programming problems, with a linear objective function. This is exactly our framework, as in [6]. First, we consider a relaxed integer programming problem where all the restrictions are linear. Then we find the solution of the relaxed integer problem by computing a test set. Next, using the so-called reverse test set, we can solve the complete problem, generating paths from the solution of the relaxed problem to a solution of the complete one. These paths increase the cost function at each step. We also obtain a feasible solution with a greedy algorithm to begin with a good upper bound with respect to the cost function. A test set for a linear integer programming problem is a set of directions that can be used to design descending algorithms with respect to a linear cost function. A test set can be computed from a Gröbner basis of the toric ideal associated with the linear restrictions, with respect to an order given by the cost function. One of the most time consuming tasks in the process described above is usually the calculation of the Gröbner basis. In this paper we consider the relaxed linear integer programming problem obtained by removing the nonlinear reliability function. For this problem we explicitly give the associated Gröbner basis, and so the test set to solve the main problem. We point out that for this problem the Gröbner basis can be computed in polynomial time with respect to the number of systems n and the number of different types of available components ki for the i-th subsystem, i=1,…,n. The organization of the paper is as follows. In Section 2, we introduce the notation and describe the model of a parallel-series system with multiple component choices. In Section 3, a greedy algorithm is described in order to compute a feasible point. Section 4 is devoted to a brief introduction to the essential facts about Gröbner bases and how they can be applied to our problem. Section 5 contains our main result: a closed formula for the test set of the underlying integer linear problem. Our computational experiments are reported in Section 6, with comparisons to other exact approaches. Finally we draw some concluding remarks in Section 7.

We have presented in this paper an exact method for solving a nonlinear integer programming problem arising from the design of series-parallel reliability systems. The method is based on the construction of a test set of an integer linear problem through the theory of Gröbner bases. We provide an explicit formula of the test set. Computational experiments show that this approach improves some existing methods in the literature already applied for this problem. This paper deepens the challenge given in [21] to yield efficient algorithms for integer problems based on attractive bases.