×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
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, (), 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, (), 225-248
[11] Balinski, M.L.; Spielberg, K., Methods for integer programming: algebraic, combinatorial, and enumerative, (), 195-292
[12] Balinski, M.L.; Wolfe, P., On benders decomposition and a plant location problem, ()
[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, ()
[15] Bilde, O., Nonlinear and discrete programming, ()
[16] Bilde, O.; Krarup, J., Bestemmelse of optimal beliggenhed af produktionssteder, ()
[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, ()
[19] Burkard, R.E.; Krarup, J.; Pruzan, P.M., Efficiency and optimality in minisum, minimax 0-1 programming problems, (), Forthcoming in J. Operational Res. Soc. · Zbl 0456.90076
[20] Cherenin, V.P., Reshenie nechotorych combinatornych zadach optimalnogo planirovania metodom posledovatelnych raschetov, (), translated as
[21] Cherenin, V.P.; Chaschaturov, V.R., Reshenie metodom posledovatelnych raschetov odnogo classa zadach o razmeshenii proizvodsta, (), 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 New York · Zbl 0321.94011
[24] Cornuéjols, G., Analysis of algorithms for a class of location problem, ()
[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, () · 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, () · 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 London
[33] Ellwein, L.B., Fixed-charge location-allocation problems with capacity and configuration constraints, ()
[34] Elshafei, A.N.; Haley, K.B., Facilities location: some formulations, methods of solution, applications and computational experience, () · Zbl 0349.90065
[35] Erlenkotter, D., Preinvestment planning for capacity expansion: a multi-location dynamic model, ()
[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 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 San Francisco · Zbl 0411.68039
[46] Garfinkel, R.S.; Nemhauser, G.L., Integer programming, (1972), 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, (), 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 France
[53] Guignard, M.; Spielberg, K., Search techniques with adaptive features for certain integer and mixed integer programming problems, (), 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, () · 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 Cambridge, MA · Zbl 0533.90026
[59] Hansen, P., Two algorithms for the simple plant location problem using additive penalties, ()
[60] Hansen, P.; Kaufman, L., An algorithm for central facilities location under an investment constraint, () · 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, (), 247-254 · Zbl 0072.37804
[65] Hochbaum, D.S., Analysis of Median problems of a special structure, () · Zbl 0435.90057
[66] Hochbaum, D.S., Heuristics for the fixed cost Median problem, () · Zbl 0473.90029
[67] Hochbaum, D.S., The probabilistic asymptotic properties of some combinatorial geometric problems, ()
[68] Jacobsen, S.K., Om lokaliseringsproblemer — modeller og løsningsmetoder, ()
[69] Jacobsen, S.K., A unified approach to heuristics and algorithms for a class of uncapacitated plant location problems, ()
[70] Jacobsen, S.K.; Pruzan, P.M., Lokalisering — modeller & løsningsmetoder, (1978), 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, () · Zbl 0461.90025
[74] Karp, R.M., Reducibility among combinatorial problems, (), 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, ()
[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.
[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, ()
[81] Krarup, J.; Bilde, O., Plant location, set covering and economic lot size: an O(mn)-algorithm for structured problems, (), 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, (), Submitted for publication · Zbl 0614.90031
[85] Krarup, J.; Pruzan, P.M., A synthesis of 25 works on locational decisions and related areas, (), 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, ()
[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, (), 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, (), 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, () · 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 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, (), 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, ()
[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, () · 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.
[121] Wolsey, L.A., Maximizing real-valued submodular functions: primal and dual heuristics for location problems, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.