A modification of the greedy procedure for solving a nonlinear knapsack class of reliability optimization problems

A number of heuristic methods that belong to the greedy procedure have been applied to a nonlinear knapsack type of reliability optimization problems. This paper shows that in the viewpoint of quality of solutions, most of these methods should be applied to general reliability optimization problems (Non-DGR type knapsack problems). In this paper, a new heuristic algorithm, which is called recursive greedy, is proposed for solving Non-DGR type knapsack problems. The algorithm first checks feasibility of alternatives for given problem, and removes infeasible alternatives from the sets of alternatives. Secondly, the algorithm checks the incremental gain ratio of objective function to constraint function between the alternatives, and reduces the problem to DGR type problem using the LP dominance. Thirdly, the algorithm continues to allocate the increments for current sets of alternatives (greedy procedure), and stops incremental allocation for the alternatives when the constraint condition is violated. With the current solution, the method then repeats the greedy procedure recursively for current alternatives, which are added to the alternatives removed by the LP dominance in the previous step. Computational results show the recursive greedy procedure is more effective than the methods reported previously. [In Japanese.]