×

A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables. (English) Zbl 0853.90116

Summary: We show that the production-transportation problem involving an arbitrary fixed number of factories with concave production cost is solvable in strongly polynomial time. The algorithm is based on a parametric approach which takes full advantage of the specific structure of the problem: monotonicity of the objective function along certain directions, small proportion of nonlinear variables and combinatorial properties implied by transportation constraints.

MSC:

90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B80 Discrete location and assignment
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M.L. Balinski, ”The Hirsch conjecture for dual transportation polyhedra,” Collaborative paper, bf CP-83-9, IIASA, Laxenburg, Austria (1983).
[2] M.S. Bazaraa and J.J. Jarvis,Linear Programming and Network Flows (Wiley, New York, 1977). · Zbl 1060.90688
[3] P.C. Chen and P. Hansen, ”On-line and off-line vertex enumeration by adjacency lists,”Operations Research Letters 10 (1991) 403–409. · Zbl 0774.90055 · doi:10.1016/0167-6377(91)90042-N
[4] M.A. Efroymson and T.R. Ray, ”A branch and bound algorithm for plant location,”Operations Research 14 (1966) 361–368. · doi:10.1287/opre.14.3.361
[5] E. Feldman, F.A. Lehrer and T.L. Ray, ”Warehouse location under continuous economies of scale,”Management Science 12 (1966) 670–684. · doi:10.1287/mnsc.12.9.670
[6] M. Florian and M. Klein, ”Deterministic production planning with concave costs and capacity constraints”,Management Science 18 (1971) 12–20. · Zbl 0273.90023 · doi:10.1287/mnsc.18.1.12
[7] G.M. Guisewite and P.M. Pardalos, ”A polynomial time solvable concave network flow problem,”Networks 23 (1990) 143–147. · Zbl 0780.90037 · doi:10.1002/net.3230230208
[8] G.M. Guisewite and P.M. Pardalos, ”Minimum concave cost network flow problems: applications, complexity and algorithms,”Annals of Operations Research 25 (1990) 75–100. · Zbl 0724.90022 · doi:10.1007/BF02283688
[9] S.L. Hakimi and C.C. Kuo, ”On a general network location-production-allocation problem,”European Journal of Operations Research 55 (1991) 31–45. · Zbl 0744.90047 · doi:10.1016/0377-2217(91)90189-3
[10] D.S. Hochbaum and J.G. Shantikumar, ”Convex separable optimization is not much harder than linear optimization,”Journal of the Association for Computing Machinery 37 (1990) 343–362. · Zbl 0721.90060
[11] R. Horst and H. Tuy,Global Optimization (Springer, Berlin, 1990). · Zbl 0704.90057
[12] B.M. Khumawala and D.L. Kelly, ”Warehouse location with concave costs,”INFOR 12 (1974) 55–65.
[13] B. Klinz and H. Tuy, ”Minimum concave cost network flow problems with a single nonlinear arc cost,” P.M. Pardalos and D.-Z. DuNetwork Optimization Problems, (World Scientific, Singapore, 1992) pp. 125–143.
[14] H. Konno ”Minimum concave cost production system: a further generalization of multiechelon model,”Mathematical Programming 41 (1988) 185–193. · Zbl 0662.90037 · doi:10.1007/BF01580763
[15] P. Krarup and P.M. Pruzan, ”The simple plant location problem: survey and synthesis,”European Journal of Operations Research 12 (1983) 36–81. · Zbl 0506.90018 · doi:10.1016/0377-2217(83)90181-9
[16] H.W. Lenstra Jr., ”Integer programming with a fixed number of variables,”Mathematics of Operations Research 8 (1983) 538–548. · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[17] L. Lovász and H.E. Scarf, ”The generalized basis reduction algorithm,”Mathematics of Operations Research 17 (1992) 751–764. · Zbl 0774.90060 · doi:10.1287/moor.17.3.751
[18] T.L. Magnanti and R.T. Wong, ”Network design and transportation planning: models and algorithms,”Transportation Science 18 (1984) 1–55. · doi:10.1287/trsc.18.1.1
[19] A.S. Nemirowsky and D.D. Yudin,Problem Complexity and Method Efficiency in Optimization (Wiley, New York, 1983).
[20] P.M. Pardalos and S.A. Vavasis, ”Quadratic programming with one negative eigenvalue is NP-hard,”Journal of Global optimization 1 (1991) 15–22. · Zbl 0755.90065 · doi:10.1007/BF00120662
[21] P.M. Pardalos and S.A. Vavasis, ”Open questions in complexity theory for nonlinear optimization,”Mathematical Programming 57 (1992) 337–339. · Zbl 0784.90102 · doi:10.1007/BF01581088
[22] J.F. Shapiro,Mathematical Programming Structures and Algorithms (Wiley, New York, 1979). · Zbl 0502.90054
[23] R.M. Soland, ”Optimal facility location with concave costs,”Operations Research 22 (1974) 373–382. · Zbl 0278.90079 · doi:10.1287/opre.22.2.373
[24] E. Tardos, ”A strongly polynomial minimum cost circulation algorithm,”Combinatorica 5 (1985) 247–255. · Zbl 0596.90030 · doi:10.1007/BF02579369
[25] T.V. Thieu, ”Solving the lay-out planning problem with concave cost”, in:Essays in Nonlinear Analysis and Optimization (Institute of Mathematics, Hanoi, 1987) pp. 101–110.
[26] H. Tuy, ”Concave minimization under linear constraints with special structure,”Optimization 16 (1985) 335–352. · Zbl 0584.90080 · doi:10.1080/02331938508843024
[27] H. Tuy, N.D. Dan and S. Ghannadan, ”Strongly polynomial algorithms for certain concave minimization problems on networks,”Operations Research Letters, 14 (1993) 99–109. · Zbl 0794.90015 · doi:10.1016/0167-6377(93)90102-M
[28] H. Tuy, S. Ghannadan, A. Migdalas and P. Värbrand, ”Strongly polynomial algorithm for a production-transportation problem with concave production costs,”Optimization 27 (1992) 205–228. · Zbl 0818.65052 · doi:10.1080/02331939308843882
[29] H. Tuy, S. Ghannadan, A. Migdalas and P. Värbrand, ”Minimum concave cost network flow problems with a fixed number of nonlinear arc costs and sources,”Journal of Global Optimization 6 (1992) 135–151. · Zbl 0833.90039 · doi:10.1007/BF01096764
[30] H. Tuy, S. Ghannadan, A. Migdalas and P. Värbrand, ”Strongly polynomial algorithm for two special minimum concave cost network flow problems,”Optimization 32 (1995) 23–43. · Zbl 0817.65049 · doi:10.1080/02331939508844033
[31] H. Tuy and B.T. Tam, ”An efficient solution method for rank two quasi-concave minimization problems,”Optimization 24 (1992) 43–56. · Zbl 0817.90079 · doi:10.1080/02331939208843778
[32] H.M. Wagner and T.M. Whitin, ”Dynamic version of the economic lot size model,”Management Science 5 (1959) 89–96. · Zbl 0995.90553 · doi:10.1287/mnsc.5.1.89
[33] S.W. Wallace, ”Decomposition of the requirement space of a transportation problem into polyhedral cones,”Mathematical Programming Study 28 (1986) 29–47. · Zbl 0599.90078
[34] W.I. Zangwill, ”A Backlogging Model and a multi-echelon model of a dynamic economic lot size production system–a network approach,”Management Science 15 (1969) 509–527. · Zbl 0172.44603 · doi:10.1287/mnsc.15.9.506
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.