Minimum concave-cost network flow problems: Applications, complexity, and algorithms

G. M. Guisewite; P. M. Pardalos

doi:10.1007/bf02283688

journal article Dec 01, 1990

Minimum concave-cost network flow problems: Applications, complexity, and algorithms

G. M. Guisewite P. M. Pardalos

Annals of Operations Research Vol. 25 No. 1 pp. 75-99 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf02283688

Topics

No keywords indexed for this article. Browse by subject →

References

108

[1]

U. Akinc and B.M. Khumawala, An efficient branch and bound algorithm for the capacitated warehouse location problem, Management Sci. 23 (1977) 585–594. 10.1287/mnsc.23.6.585

[2]

A. Balakrishnan and S.C. Graves, A composite algorithm for a concave-cost network flow problem, Networks 19 (1989) 175–202. 10.1002/net.3230190202

[3]

Fixed‐cost transportation problems

Michel L. Balinski

Naval Research Logistics Quarterly 1961 10.1002/nav.3800080104

[4]

M.L. Balinski and R.E. Quandt, On an integer program for a delivery problem. Oper. Res. 12 (1964) 300–304. 10.1287/opre.12.2.300

[5]

R.S. Barr, F. Glover and D. Klingman, A new optimization method for large scale fixed charge transportation problems. Oper. Res. 29 (1981) 448–463. 10.1287/opre.29.3.448

[6]

W.J. Baumol and P. Wolfe, A warehouse-location problem Oper. Res. 6 (1958) 252–263. 10.1287/opre.6.2.252

[7]

I. Baybars and R.H. Edahl, A heuristic method for facility planning in telecommunications networks with multiple alternate routes, Naval Res. Logistics Quarterly 35 (1988) 503–528. 10.1002/1520-6750(198808)35:4<503::aid-nav3220350406>3.0.co;2-n

[8]

D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation (Prentice Hall, New Jersey, 1989).

[9]

H.L. Bhatia, Indefinite quadratic solid transportation problem, J. Inform. Optimiz. Sci. 2 (1981) 297–303.

[10]

C.T. Bornstein and R. Rust, Minimizing a sum of staircase functions under linear constraints, Optimization 19 (1988) 181–190. 10.1080/02331938808843335

[11]

V.P. Bulatov, The immersion method for the global minimization of functions on the convex polyhedra,Int. Symp. on Engineering, Mathematics, and Applications, Beijing, PR China (July 1988) pp. 335–338.

[12]

A.V. Cabot and S.S. Erenguc, Some branch-and-bound procedures for fixed-cost transportation problems, Naval Res. Logistics Quarterly 31 (1984) 145–154. 10.1002/nav.3800310115

[13]

L. Cooper and C. Drebes, An approximate solution method for the fixed-charge problem. Naval Res. Logistics Quarterly 14 (1968) 101–113. 10.1002/nav.3800140110

[14]

G. Daeninck and Y. Smeers, Using shortest paths in some transshipment problems with concave costs, Math. Programming (1977) 18–25. 10.1007/bf01593766

[15]

G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, New Jersey, 1963).

[16]

P.S. Davis and T.L. Ray, A branch-and-bound algorithm for the capacitated facilities locations problem, Naval Res. Logistics Quarterly 16 (1969) 331–344. 10.1002/nav.3800160306

[17]

D.R. Denzler, An approximate algorithm for the fixed charge problems, Naval Res. Logistics Quarterly 16 (1969) 411–416. 10.1002/nav.3800160311

[18]

An Algorithm for the Solution of Mixed Integer Programming Problems

Norman J. Driebeek

Management Science 1966 10.1287/mnsc.12.7.576

[19]

M.A. Efroymson and T.L. Ray, A branch-and-bound algorithm for plant location. Oper. Res. 14 (1966) 361–368. 10.1287/opre.14.3.361

[20]

H.G. Eggleston,Convexity, Cambridge Tracts in Mathematics and Mathematical Physics No. 47 (Cambridge University Press, Cambridge, MA, 1963).

[21]

R.E. Erickson, C.L. Monma and A.F. Veinott, Jr., Send-and-split method for minimum-con-cave-cost network flows, Math. Oper. Res. 12 (1987) 634–664. 10.1287/moor.12.4.634

[22]

D. Erlenkotter, Two producing areas—dynamic programming solutions, in:Investment for Capacity Expansion: Size, Location and Time Phasing, ed. A.S. Manne (MIT Press, Cambridge, MA, 1967) pp. 210–227.

[23]

J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems. Management Sci. 15 (1969) 550–569. 10.1287/mnsc.15.9.550

[24]

M. Florian, An introduction to network models used in transportation planning,Transportation Planning Models (Elsevier, New York, 1984).

[25]

M. Florian, Nonlinear cost network models in transportation analysis, Math. Programming Study 26 (1986) 167–196. 10.1007/bfb0121092

[26]

M. Florian and M. Klein, Deterministic production planning with concave costs and capacity constraints. Management Sci. 18 (1971) 12–20. 10.1287/mnsc.18.1.12

[27]

M. Florian, J.K. Lenstra and A.H.G. Rinnooy Kan. Deterministic production planning: algorithms and complexity, Management Sci. 26 (1980) 669–679. 10.1287/mnsc.26.7.669

[28]

M. Florian and P. Robillard, An implicit enumeration algorithm for the concave cost network flow problem, Management Sci. 18 (1971) 184–193. 10.1287/mnsc.18.3.184

[29]

M. Florian, M. Rossin-Arthiat, and D. de Werra, A property of minimum concave cost flows in capacitated networks, Can. J. Oper. Res. 9 (1971) 293–304.

[30]

C.O. Fong and M.R. Rao, Capacity expansion with two producing regions and concave costs, Management Sci. 22 (1975) 331–339. 10.1287/mnsc.22.3.331

[31]

L.R. Ford, jr. and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, New Jersey, 1962).

[32]

G. Gallo, C. Sandi and C. Sodini, An algorithm for the min concave-cost flow problem, Europ. J. Oper. Res. 4 (1980) 249–255. 10.1016/0377-2217(80)90109-5

[33]

G. Gallo and C. Sodini, Adjacent extreme flows and application to min concave-cost flow problems. Networks 9 (1979) 95–121. 10.1002/net.3230090202

[34]

M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, CA, 1979).

[35]

S.C. Graves and J.B. Orlin, A minimum concave-cost dynamic network flow problem with an application to lot-sizing. Networks, 15 (1985) 59–71. 10.1002/net.3230150107

[36]

P. Gray, Exact solution of the site selection problem by mixed integer programming, in:Applications of Mathematical Programming Techniques, ed. E.M.L. Beale (The English Universities Press, London, 1970) pp. 262–270.

[37]

P. Gray, Exact solution of the fixed-charge transportation problem. Oper. Res. 19 (1971) 1529–1538. 10.1287/opre.19.6.1529

[38]

G.M. Guisewite and P.M. Pardalos, Algorithms for the uncapacitated single-source minimum concave-cost network flow problem, Technical Report, Department of Computer Science, Pennsylvania State University (1990). 10.1007/bf00119934

[39]

New Methods in Mathematical Programming—The Solid Transportation Problem

K. B. Haley

Operations Research 1962 10.1287/opre.10.4.448

[40]

R.W. Hall, Graphical interpretation of the transportation problem, Transportation Sci. 23 (1988) 37–45. 10.1287/trsc.23.1.37

[41]

G.L. Hefley and B.O. Barr, Fixed charge transportation problem: a survey, presented to the 43rd ORSA National Meeting in Milwaukee, Wisconsin (May 1973).

[42]

D.S. Hochbaum and A. Segev. Analysis of a flow problem with fixed charges. Networks 19 (1989) 291–312. 10.1002/net.3230190304

[43]

R. Horst and H. Tuy,Global Optimization: Deterministic Approaches. (Springer, 1989) to be published. 10.1007/978-3-662-02598-7

[44]

T. Ibaraki and N. Katoh,Resource Allocation Problems, Algorithmic Approaches (The MIT Press, Cambridge, MA., 1988).

[45]

J.J. Jarvis, V.E. Unger, R.L. Rardin and R.W. Moore, Optimal design of regional wastewater systems: a fixed charge network flow model. Oper. Res. 26 (1978) 538–550. 10.1287/opre.26.4.538

[46]

R. Jogannathan and M.R. Rao, A class of deterministic production planning models, Management Sci. 19 (1973) 1295–1300. 10.1287/mnsc.19.11.1295

[47]

L.A. Johnson and D.C. Montgomery,Operations Research in Production Planning, Scheduling, and Inventory Control. (Wiley, New York, 1974) pp. 212–224.

[48]

D. Kennedy, Some branch-and-bound techniques for nonlinear optimization, Math. Programming 42 (1988) 147–169. 10.1007/bf01589399

[49]

J. Kennington, The fixed-charge transportation problem: a computational study with a branch-and-bound code. AIIE Trans. 8 (1976) 241–247. 10.1080/05695557608975073

[50]

J. Kennington and E. Unger, The group-theoretic structure in the fixed-charge transportation problem. Oper. Res. 21 (1973) 1142–1152. 10.1287/opre.21.5.1142

Showing 50 of 108 references

Cited By

150

Piecewise linear neural networks and deep learning

Qinghua Tao, Li Li · 2022

Nature Reviews Methods Primers

Offloading in Internet of Vehicles: A Fog-Enabled Real-Time Traffic Management System

Xiaojie Wang, Zhaolong Ning · 2018

IEEE Transactions on Industrial Inf...

Metrics

150

Citations

108

References

Details

Published: Dec 01, 1990
Vol/Issue: 25(1)
Pages: 75-99
License: View

Authors

Cite This Article

G. M. Guisewite, P. M. Pardalos (1990). Minimum concave-cost network flow problems: Applications, complexity, and algorithms. Annals of Operations Research, 25(1), 75-99. https://doi.org/10.1007/bf02283688

Minimum concave-cost network flow problems: Applications, complexity, and algorithms

You May Also Like