|
Minimum cost to reliability ratio path problem R.K. Ahuja, Computers and Operations Research 15, 83-89, 1988 The minimum ratio path problem in a network is known to be a strong NP-complete problem. However its variant, the minimum cost-reliability ratio path problem, is shown to possess an entirely different structure. We observe that the optimum solution of the minimum cost-reliability ratio path problem is an efficient extreme solution of a bicriteria path problem. We employ parametric programming to enumerate these efficient extreme solutions and a sufficiency condition is used to cut down the enumeration substantially. The algorithm is shown to be pseudo-polynomial. Computational results of the algorithm on grid as well as random networks are also presented. The algorithm is able to solve problems with several thousand nodes and arcs in a few seconds. |