A STRONGLY POLYNOMIAL ALGORITHM FOR A CONCAVE PRODUCTION-TRANSPORTATION PROBLEM WITH A FIXED NUMBER OF NONLINEAR VARIABLES

Authors
TUY H GHANNADAN S MIGDALAS A VARBRAND P
Citation
H. Tuy et al., A STRONGLY POLYNOMIAL ALGORITHM FOR A CONCAVE PRODUCTION-TRANSPORTATION PROBLEM WITH A FIXED NUMBER OF NONLINEAR VARIABLES, Mathematical programming, 72(3), 1996, pp. 229-258
Citations number
34
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
72
Issue
3
Year of publication
1996
Pages
229 - 258
Database
ISI
SICI code
0025-5610(1996)72:3<229:ASPAFA>2.0.ZU;2-S
Abstract
We show that the production-transportation problem involving an arbitr ary fixed number of factories with concave production cost is solvable in strongly polynomial time. The algorithm is based on a parametric a pproach which takes full advantage of the specific structure of the pr oblem: monotonicity of the objective function along certain directions , small proportion of nonlinear variables and combinatorial properties implied by transportation constraints.