×

The simple plant location problem: Survey and synthesis. (English) Zbl 0506.90018


MSC:

90B05 Inventory, storage, reservoirs
90C10 Integer programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C90 Applications of mathematical programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akinc, U.; Khumawala, B. M., An efficient branch and bound algorithm for the capacitated warehouse location problem, Management Sci., 23, 585-594 (1977) · Zbl 0348.90157
[2] Babayev, Dj. A., Comments on the note of Frieze, Math. Programming, 1, 249-252 (1974) · Zbl 0294.90056
[3] Baker, K. R., A heuristic approach to locating a fixed number of facilities, Logist. Transportation Rev., 10, 195-205 (1974)
[4] Balas, E., An additive algorithm for solving linear programs with zero-one variables, Operations Res., 13, 517-545 (1965) · Zbl 0194.19903
[5] Balas, E.; Padberg, M. W., On the set covering problem, Operations Res., 20, 1152-1161 (1972) · Zbl 0254.90035
[6] Balas, E.; Padberg, M. W., On the set covering problem: II. An algorithm for set partitioning, Operation Res., 23, 74-90 (1975) · Zbl 0324.90045
[7] Balas, E.; Padberg, M. W., Set partitioning, (Roy, B., Combinatorial Programming: Methods and Applications (1975), D. Reidel: D. Reidel Dordrecht, Holland), 205-258
[8] Balas, E.; Padberg, M. W., Set partitioning: a survey, SIAM Rev., 18, 710-760 (1976) · Zbl 0347.90064
[9] Balinski, M. L., Integer programming: methods, uses, computation, Management Sci., 12, 253-313 (1965) · Zbl 0129.12004
[10] Balinski, M. L., On finding integer solutions to linear programs, (Proc. IBM Scientific Symposium on Combinatorial Problems (1966), IBM: IBM White Plains, NY), 225-248
[11] Balinski, M. L.; Spielberg, K., Methods for integer programming: algebraic, combinatorial, and enumerative, (Aronofsky, J. S., Progress in Operations Research III (1969), Wiley: Wiley New York), 195-292
[12] Balinski, M. L.; Wolfe, P., On Benders decomposition and a plant location problem, (Working paper ARO-27 (1963), Mathematica: Mathematica Princeton, NJ)
[13] Baumol, W. J.; Wolfe, P., A warehouse location problem, Operations Res., 6, 252-253 (1958) · Zbl 1414.90190
[14] Bergendahl, G., Models for capacity planning, (Ph.D. thesis (1966), Department of Business Administration, University of Lund: Department of Business Administration, University of Lund Sweden)
[15] Bilde, O., Nonlinear and discrete programming, (Ph.D. thesis (1970), IMSOR, Technical University of Denmark)
[16] Bilde, O.; Krarup, J., Bestemmelse of optimal beliggenhed af produktionssteder, (Research report (1967), IMSOR, Technical University of Denmark)
[17] Bilde, O.; Krarup, J., Sharp lower bounds and efficient algorithms for the simple plant location problem, Ann. Discrete Math., 1, 79-97 (1977)
[18] Booth, K. S., PQ-tree algorithms, (Ph.D. thesis (1975), Department of Electrical Engineering and Computer Science, University of California: Department of Electrical Engineering and Computer Science, University of California Berkeley, CA)
[19] Burkard, R. E.; Krarup, J.; Pruzan, P. M., Efficiency and optimality in minisum, minimax 0-1 programming problems, (Report 80-9 (1981), Mathematical Institute, University of Cologne), Forthcoming in J. Operational Res. Soc. · Zbl 0456.90076
[20] Cherenin, V. P., Reshenie nechotorych combinatornych zadach optimalnogo planirovania metodom posledovatelnych raschetov, (Proc. Conference on Experiences and Perspectives of the Application of Mathematical Methods and Electronic Computers in Planning. Proc. Conference on Experiences and Perspectives of the Application of Mathematical Methods and Electronic Computers in Planning, Novosibirsk (1962)), translated as
[21] Cherenin, V. P.; Chaschaturov, V. R., Reshenie metodom posledovatelnych raschetov odnogo classa zadach o razmeshenii proizvodsta, (Economics and Mathematical Methods, 2 (1965), Science: Science Moscow), translated as
[22] Chern, W. S.; Polopolus, L., Discontinuous plant cost functions and a modification of the Stollsteimer location model, Amer. J. Agricult. Econom., 52, 581-586 (1970)
[23] Christofides, N., Graph Theory: An Algorithmic Approach (1975), Academic Press: Academic Press New York · Zbl 0321.94011
[24] Cornuéjols, G., Analysis of algorithms for a class of location problem, (Technical report no. 382 (1978), SORIE, Cornell University)
[25] Cornuéjols, G.; Fisher, M. L.; Nemhauser, G. L., On the uncapacitated location problem, Ann. Discrete Math., 1, 163-177 (1977)
[26] Cornuéjols, G.; Fisher, M. L.; Nemhauser, G. L., Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms, Management Sci., 23, 789-810 (1977) · Zbl 0361.90034
[27] Cornuéjols, G.; Nemhauser, G. L.; Wolsey, L. A., A canonical representation of simple plant location problems and its applications, (Technical report no. 428 (1979), SORIE, Cornell University) · Zbl 0501.90032
[28] Cornuéjols, G.; Nemhauser, G. L.; Wolsey, L. A., Worst-case and probabilistic analyses of algorithms for a location problem, Operations Res., 28, 847-858 (1980) · Zbl 0441.90027
[29] Cornuéjols, G.; Thizy, J.-M., Some facets of the simple plant location polytope, (Working paper WP 39-79-80 (1981), GSIA, Carnegie-Mellon University) · Zbl 0485.90069
[30] Davis, P. S.; Ray, T. L., A branch-bound algorithm for the capacitated facilities location problem, Naval Res. Logist. Quart., 16, 331-344 (1969) · Zbl 0186.24905
[31] Efroymson, M. A.; Ray, T. L., A branch-bound algorithm for plant location, Operations Res., 14, 361-368 (1966)
[32] Eilon, S.; Watson-Gandy, C. D.T.; Christofides, N., Distribution Management: Mathematical Modelling and Practical Analysis (1971), Griffin: Griffin London
[33] Ellwein, L. B., Fixed-charge location-allocation problems with capacity and configuration constraints, (Technical Report 70-2 (1970), Department of Industrial Engineering, Stanford University)
[34] Elshafei, A. N.; Haley, K. B., Facilities location: some formulations, methods of solution, applications and computational experience, (OR report no. 90 (1974), University of Birmingham) · Zbl 0349.90065
[35] Erlenkotter, D., Preinvestment planning for capacity expansion: a multi-location dynamic model, (Ph.D. thesis (1969), Stanford University)
[36] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Res., 26, 992-1009 (1978) · Zbl 0422.90053
[37] Feldman, E.; Lehrer, F. A.; Ray, T. L., Warehouse location under continuous economies of scale, Management Sci., 12, 670-684 (1966)
[38] Fisher, M. L., Worst-case analysis of heuristic algorithms, Management Sci., 26, 1-17 (1980) · Zbl 0448.90041
[39] Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Management Sci., 27, 1-18 (1981) · Zbl 0466.90054
[40] Fisher, M. L.; Hochbaum, D. S., Probabilistic analysis of the planar \(k\)-median problem, Math. Operations Res., 5, 27-34 (1980) · Zbl 0435.90057
[41] Fisher, M. L.; Nemhauser, G. L.; Wolsey, L. A., An analysis of approximations for maximizing submodular set functions — II, Math. Programming Study, 8, 73-87 (1978) · Zbl 0408.90085
[42] Francis, R. L.; White, J. A., Facility Layout and Location: An Analytical Approach (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[43] Frieze, A. M., A cost function property for plant location problems, Math. Programming, 7, 245-248 (1974) · Zbl 0292.90039
[44] Galvão, R. D., A dual-bounded algorithm for the \(p\)-median problem, Operations Res., 28, 1112-1121 (1980) · Zbl 0451.90040
[45] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[46] Garfinkel, R. S.; Nemhauser, G. L., Integer Programming (1972), Wiley: Wiley New York · Zbl 0271.90028
[47] Geoffrion, A. M., Lagrangian relaxation for integer programming, Math. Programming Study, 2, 82-114 (1974) · Zbl 0395.90056
[48] Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by Benders decomposition, Management Sci., 20, 822-844 (1974) · Zbl 0304.90122
[49] Geoffrion, A. M.; McBride, R., Lagrangian relaxation applied to capacitated facility location problems, AIIE Trans., 10, 40-47 (1978)
[50] Gray, P., Exact solution of the site selection problem by mixed integer programming, (Beale, E. M.L., Applications of Mathematical Programming Techniques (1970), English Universities Press: English Universities Press London), 261-270
[51] Guignard, M., Fractional vertices, cuts and facets of the simple plant location problem, Math. Programming Study, 12, 150-162 (1980) · Zbl 0439.90061
[52] Guignard-Spielberg, M., Contribution a l’etude de l’optimisation en nombres entiers et de l’optimalité en programmation mathématique, No d’ordre: 482 (1980), L’Université des sciences et techniques de Lille: L’Université des sciences et techniques de Lille France
[53] Guignard, M.; Spielberg, K., Search techniques with adaptive features for certain integer and mixed integer programming problems, (Proc. IFIP Congress. Proc. IFIP Congress, Edinburgh (1969), North-Holland: North-Holland Amsterdam), 238-244, 1968
[54] Guignard, M.; Spielberg, K., Algorithms for exploiting the structure of the simple plant location problem, Ann. Discrete Math., 1, 247-271 (1977)
[55] Guignard, M.; Spielberg, K., A direct dual method for the mixed plant location problem with some side constraints, Math. Programming, 17, 198-228 (1979) · Zbl 0416.90052
[56] Guignard, M.; Spielberg, K., A direct dual approach to a transshipment formulation for multi-layer problems with fixed charges, (Technical Report 43 (1979), Department of Statistics, The Wharton School, University of Pennsylvania) · Zbl 0203.48801
[57] Hammer, P. L., Plant location — a pseudo-boolean approach, Israel J. Tech., 6, 330-332 (1968) · Zbl 0238.90045
[58] Handler, G. Y.; Mirchandani, P. B., Location on Networks: Theory and Algorithms (1979), MIT-Press: MIT-Press Cambridge, MA · Zbl 0533.90026
[59] Hansen, P., Two algorithms for the simple plant location problem using additive penalties, (Presented at the European Congress of the Econometric Society. Presented at the European Congress of the Econometric Society, Budapest (1972))
[60] Hansen, P.; Kaufman, L., An algorithm for central facilities location under an investment constraint, (Van Moeseke, P., Mathematical Programs for Activity Analysis (1972), North-Holland: North-Holland Amsterdam) · Zbl 0365.90048
[61] Hansen, P.; Thisse, J.-F., Multiplant location for profit maximization, Environment and Planning A, 9, 63-73 (1977)
[62] Hansen, P.; Thisse, J.-F.; Hanjoul, P., Simple plant location under uniform delivered pricing, European J. Operational Res., 6, 94-103 (1981) · Zbl 0451.90035
[63] Held, M.; Karp, R. M., The traveling-salesman and minimum spanning trees: part II, Math. Programming, 1, 6-25 (1971) · Zbl 0232.90038
[64] Heller, I.; Tompkins, C. B., An extension of a theorem of Dantzig’s, (Kuhn, H. W.; Tucker, A. W., Linear Inequalities and Related Systems (1956), Princeton University Press: Princeton University Press Princeton, NJ), 247-254 · Zbl 0072.37804
[65] Hochbaum, D. S., Analysis of median problems of a special structure, (Ph.D. thesis (1978), Decision Sciences, The Wharton School, University of Pennsylvania) · Zbl 0435.90057
[66] Hochbaum, D. S., Heuristics for the fixed cost median problem, (W.P. 55-78-79 (1979), GSIA, Carnegie-Mellon University) · Zbl 0473.90029
[67] Hochbaum, D. S., The probabilistic asymptotic properties of some combinatorial geometric problems, (W.P. 30-79-80 (1980), GSIA, Carnegie-Mellon University)
[68] Jacobsen, S. K., Om lokaliseringsproblemer — modeller og løsningsmetoder, (Ph.D. thesis (1973), IMSOR, Technical University of Denmark)
[69] Jacobsen, S. K., A unified approach to heuristics and algorithms for a class of uncapacitated plant location problems, (Working paper (2252) (1977), IMSOR, Technical University of Denmark)
[70] Jacobsen, S. K.; Pruzan, P. M., Lokalisering — modeller & løsningsmetoder (1978), Studentlitteratur: Studentlitteratur Lund, Sweden
[71] Juel, H., Bounds in the location-allocation problem, J. Regional Sci., 21, 277-282 (1981)
[72] Jucker, J. V.; Carlson, R. C., The simple plant-location problem under uncertainty, Operations Res, 24, 1045-1055 (1976) · Zbl 0343.90054
[73] Karkazis, J.; Boffey, T. B., The multi-commodity facilities location problem, (Presented at the V Symposium über Operations Research. Presented at the V Symposium über Operations Research, Cologne (1980)) · Zbl 0461.90025
[74] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[75] Karp, R. M., Probabilistic analysis of partitioning algorithms for the traveling-sales man problem in the plane, Math. Operations Res., 2, 209-224 (1977) · Zbl 0391.90091
[76] Kaufman, L., The location of economic activities by 0-1 programming, (Doctoral thesis (1975), Faculteit der Wetenschappen, Vrije Universiteit Brussel)
[77] Khumawala, B. M., An efficient branch and bound algorithm for the warehouse location problem, Management Sci., 18, 718-731 (1972)
[78] Kolen, A.W.J. (1978), Private communication.; Kolen, A.W.J. (1978), Private communication.
[79] Korte, B., Approximative algorithms for discrete optimization problems, Ann. Discrete Math., 4, 85-120 (1979) · Zbl 0411.90052
[80] Krarup, J., Fixed-cost and other network flow problems, (Ph.D. thesis (1967), IMSOR, Technical University of Denmark)
[81] Krarup, J.; Bilde, O., Plant location, set covering and economic lot size: an O(mn)-algorithm for structured problems, (Collatz, L.; etal., Optimierung bei graphentheoretischen und ganzzahligen Probleme. Optimierung bei graphentheoretischen und ganzzahligen Probleme, ISNM 36 (1977), Birkhäuser Verlag: Birkhäuser Verlag Basel), 155-180 · Zbl 0364.90067
[82] Krarup, J.; Pruzan, P. M., Selected families of location problems, Ann. Discrete Math., 5, 327-387 (1979) · Zbl 0415.90063
[83] Krarup, J.; Pruzan, P. M., Reducibility of minimax to minisum 0-1 programming problems, European J. Operational Res., 6, 125-132 (1981) · Zbl 0451.90084
[84] Krarup, J.; Pruzan, P. M., Assessment of approximate algorithms: the error measure’s crucial role, (DIKU-report 81/7 (1981), Institute of Datalogy, University of Copenhagen), Submitted for publication · Zbl 0614.90031
[85] Krarup, J.; Pruzan, P. M., A synthesis of 25 works on locational decisions and related areas, ((1981), DIKU and Institute of Economics, University of Copenhagen), Published jointly by · Zbl 0426.90022
[86] Kuehn, A. A.; Hamburger, M. J., A heuristic program for locating warehouses, Management Sci., 9, 643-666 (1963)
[87] Ladd, G. W.; Halvorson, M. P., Parametric solutions to the Stollsteimer model, Amer. J. Agricult. Econom., 52, 578-580 (1970)
[88] Lea, A. C., Location-allocation systems: an annotated bibliography, (Discussion paper no. 13 (1973), Department of Geography, University of Toronto)
[89] Lemke, C. E.; Spielberg, K., Direct search algorithm for zero-one and mixed-integer programming, Operations Res., 15, 892-914 (1967) · Zbl 0168.18201
[90] Lemke, C. E.; Salkin, H. M.; Spielberg, K., Set covering by single-branch enumeration with linear-programming subproblems, Operations Res., 19, 998-1022 (1971) · Zbl 0232.90033
[91] Lenstra, J. K.; Rinnooy Kan, A. H.G., Complexity of packing, covering and partitioning problems, (Schrijver, A., Packing and Covering in Combinatorics. Packing and Covering in Combinatorics, Mathematical Centre Tracts, 106 (1979), Mathematical Centre: Mathematical Centre Amsterdam), 275-291 · Zbl 0439.90041
[92] Manne, A. S., Plant location under economies-of-scale — decentralization and computation, Management Sci., 11, 213-235 (1964)
[93] Melnikov, D. I., Method posledovatelnych raschetov i zadachi razmeshenia proizvodstva s nefiksirovannym sprosom, (Work on Discrete Mathematics (1973)), Science, Moscow
[94] Morris, J. G., On the extent to which certain fixed-charge depot location problems can be solved by LP, J. Operational Res. Soc., 29, 71-76 (1978)
[95] Narula, S. C.; Ogbu, U. I.; Samuelson, H. M., An algorithm for the \(p\)-median problem, Operations Res., 25, 709-713 (1977) · Zbl 0372.90096
[96] Nemhauser, G. L.; Wolsey, L. A., Maximizing submodular set functions: formulations and analysis of algorithms, (Technical report no. 398 (1979), SORIE, Cornell University) · Zbl 0469.90052
[97] Nemhauser, G. L.; Wolsey, L. A., Best algorithms for approximating the maximum of a submodular set function, Math. Operations Res., 3, 177-188 (1978) · Zbl 0395.90072
[98] Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing submodular set functions — I, Math. Programming, 14, 265-294 (1978) · Zbl 0374.90045
[99] Padberg, M. W., Covering, packing, and knapsack problems, Ann. Discrete Math., 4, 265-287 (1979) · Zbl 0407.90056
[100] Pruzan, P. M., The Bangladesh grain model, European J. Operational Res., 3, 110-121 (1978)
[101] Reiter, S.; Sherman, G. R., Allocating indivisible resources affording external economies or diseconomies, Internat. Econom. Rev., 3, 108-135 (1962)
[102] ReVelle, C. S.; Marks, D.; Liebman, J. C., An analysis of private and public sector location models, Management Sci., 16, 692-707 (1970) · Zbl 0195.21901
[103] ReVelle, C. S.; Swain, R. S., Central facilities location, Geographical Anal., 2, 30-42 (1970)
[104] Rosing, K. E.; ReVelle, C. S.; Rosing-Vogelaar, H., The \(p\)-median and its linear programming relaxation: an approach to large problems, J. Operational Res., 30, 815-823 (1979) · Zbl 0422.90049
[105] Ross, G. T.; Soland, R. M., A multicriteria approach to the location of public facilities, European J. Operational Res., 4, 307-321 (1980) · Zbl 0432.90028
[106] Sá, G., Branch-and-bound and approximate solutions to the capacitated plant-location problem, Operations Res., 17, 1005-1016 (1969)
[107] Salkin, H. M., Integer Programming (1975), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0319.90038
[108] Schrage, L., Implict representation of variable upper bounds in linear programming, Math. Programming Study, 4, 118-132 (1975)
[109] Shapiro, J. F., A survey of Lagrangian techniques for discrete optimization, Ann. Discrete Math., 4, 113-138 (1979) · Zbl 0411.90054
[110] Shapley, L. S., Cores of convex games, Internat. J. Game Theory, 1, 11-26 (1962) · Zbl 0222.90054
[111] Soland, R. M., Optimal facility location with concave costs, Operations Res., 22, 373-382 (1974) · Zbl 0278.90079
[112] Spielberg, K., Algorithms for the simple plant-location problem with some side conditions, Operations Res., 17, 85-111 (1969) · Zbl 0165.54104
[113] Spielberg, K., Plant location with generalized search origin, Management Sci., 16, 165-178 (1969)
[114] Spielberg, K., On solving plant location problems, (Beale, E. M.l., Applications of Mathematical Programming Techniques (1970), English Universities Press: English Universities Press London), 216-234
[115] Stollsteimer, J. F., The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region, (Ph.D. thesis (1961), University of California: University of California Berkeley, CA)
[116] Stollsteimer, J. F., A working model for plant numbers and locations, J. Farm Econom., 45, 631-645 (1963)
[117] Van Roy, T. J.; Erlenkotter, D., A dual-based procedure for dynamic facility location, (WP-80-31 (1980), IIASA: IIASA Laxenburg) · Zbl 0495.90033
[118] Warrack, A. A.; Fletcher, L. B., Plant location model suboptimization for large problems, Amer. J. Agricult. Econom., 52, 587-590 (1970)
[119] Warszawski, A., Pseudo-boolean solutions to multidimensional location problems, Operations Res., 22, 1081-1085 (1974) · Zbl 0293.90030
[120] Wolfe, P. (1980), Private communication.; Wolfe, P. (1980), Private communication.
[121] Wolsey, L. A., Maximizing real-valued submodular functions: primal and dual heuristics for location problems, (Discussion paper 8019 (1980), CORE, Université Catholique de Louvain) · Zbl 0498.90024
[122] Zangwill, W. I., Minimum concave cost flows in certain networks, Management Sci., 14, 429-450 (1968) · Zbl 0159.49102
[123] Zimmerman, R., A branch and bound algorithm for depot location, Metra, 6, 661-674 (1967)
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.