A PSEUDO-POLYNOMIAL ALGORITHM FOR SOLVING RANK THREE CONCAVE PRODUCTION-TRANSPORTATION PROBLEMS

Dedicated to Hoang Tuy on the occasion of his seventieth birthday Abstract. In this paper, we extend the parametrization technique of Tuy et al. into a class of concave production-transportation problems with m (� 3) sources, n terminals and three nonlinear variables. We develop a depth-first-search algorithm for finding a globally optimal solution of this rank three concave minimization problem and show that the algorithm is pseudo-polynonomial in the problem input length but polynomial in m and n.