Smart greedy procedure for solving a nOnlinear knapsack class of reliability optimization problems

✍ Scribed by H. Ohtagaki; Y. Nakagawa; A. Iwasaki; H. Narihisa

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 772 KB
• Volume: 22
• Category: Article
• ISSN: 0895-7177
• DOI: 10.1016/0895-7177(95)00203-e

✦ Synopsis

new heuristic procedure, which is called Smart Greedy, is proposed for solving a kind of general reliability optimization problems (non-DGR type knapsack problems). Smart Greedy uses Recursive Greedy with multiple greedy functions designated by balance coefficients, generates several solutions, and then determines the best solution among them as the smart greedy solution. Recursive Greedy first checks the feasibility of sets of items for a given problem, and removes infeasible items from the item sets. Second, the procedure checks the gain ratio of increments of objective function to constraint function, and reduces the problem to DGR type problem by invoking LP dominance.

Third, the procedure continues to allocate the increments for current items until the constraint is violated. With the current solution, the procedure then repeats the greedy procedure for current items that are added to the items removed by the LP dominance in the previous step.

Computational results show that the Smart Greedy is more effective than the previously reported methods.