zbMATH — the first resource for mathematics

Layout of facilities with some fixed points. (English) Zbl 0608.90016
This paper deals with the location of facilities or ”movable” points on a planar area, on which there already exist fixed points. This minimax criterion for optimality is used and distances among points are assumed to be rectilinear. Two very efficient algorithms for the solution of the problem are presented. One is based on a univariate search, and the other on a steepest descent method. Some computational results are presented.

90B05 Inventory, storage, reservoirs
65K05 Numerical mathematical programming methods
Algorithm 431
Full Text: DOI
[1] Bandler, J.W.; Srinivasan, T.V.; Charalambus, C., Minimax optimization of networks by grazor search, IEEE trans. microwave theory tech., 20, 596-604, (1972)
[2] Beale, E.M.L., Mathematical programming in practice, (1968), John Wiley New York · Zbl 0333.65029
[3] Dantzig, G.B.; Cottle, W., Complementary pivot theory of mathematical programming, J. linear algebra appl., 1, 103-125, (1968) · Zbl 0155.28403
[4] Demjanov, V.F., Algorithms for some minimax problems, J. comput. systems sci., 2, 342-380, (1968) · Zbl 0177.23104
[5] Drezner, Z., DISCON—A new method for the layout problem, Oper. res., 28, 1375-1384, (1980) · Zbl 0447.90025
[6] Drezner, Z.; Wesolowsky, G.O., A new method for the multifacility minimax location problem, J. oper. res. soc., 29, 1095-1101, (1978) · Zbl 0388.90092
[7] Drezner, Z.; Wesolowsky, G.O., Single facility lp distance minimax location, SIAM J. alg. discrete methods, 1, 315-321, (1980) · Zbl 0501.90031
[8] Ishizaki, Y.; Watanabe, H., An iterative Chebyshev approximation method for network design, IEEE trans. cire. theory, CT-15, 326-336, (1968)
[9] Lemke, C.; Howson, J.T., Equilibrium points of bimatrix games, J. SIAM, 12, 413-423, (1964) · Zbl 0128.14804
[10] Megiddo, N., The weighted Euclidean one-center problem, Math. oper. res., 8, 498-504, (1983) · Zbl 0533.90030
[11] Megiddo, N., Linear programming in linear time when the dimension is fixed, J. ACM, 31, 114-127, (1984) · Zbl 0637.90064
[12] Osborn, M.R.; Watson, G.A., An algorithm for minimax approximation in the nonlinear case, Comput. J., 12, 63-68, (1969) · Zbl 0164.45802
[13] Picard, J.C.; Ratliff, H.D., A cut approach to the rectilinear distance facility location, Oper. res., 26, 422-433, (1978) · Zbl 0381.90090
[14] Ravindran, A., Algorithm 431: A computer routine for quadratic and linear programming problems, Commun. ACM, 15, 818-820, (1972)
[15] Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 382-398, (1959) · Zbl 0103.37603
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.