GBSSS: The generalized big square small square method for planar single- facility location.

*(English)*Zbl 0760.90067Summary: Big Square Small Square is a geometrical branch-and-bound algorithm, devised by P. Hansen, D. Peeters, D. Richard and J.-F. Thisse [Oper. Res. 33, 1251-1265 (1985; Zbl 0582.90027)], for the solution of constrained planar minisum single-facility location problems with \(L_ p\) norms and continuous non-decreasing costfunctions. The method basically works by splitting the studied planar region into squares, and either rejecting or further processing these squares by the evaluation of a lower bound. We present a modified version of this algorithm aimed at correcting a small failure to converge, accelerating the calculations, minimising the information to be stored, and, most importantly, determining a region of near-optimality. Furthermore the method is applicable to any planar single-facility problem with distances measured by mixed norms and as an objective any continuous function of the distances. This includes nearly all the models which have been proposed in the literature.

##### MSC:

90B85 | Continuous location |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

##### Keywords:

geometrical branch-and-bound algorithm; region of near-optimality; planar single-facility; mixed norms
PDF
BibTeX
XML
Cite

\textit{F. Plastria}, Eur. J. Oper. Res. 62, No. 2, 163--174 (1992; Zbl 0760.90067)

Full Text:
DOI

##### References:

[1] | Cooper, L., The transportation-location problem, Operations research, 20, 94-108, (1972) · Zbl 0237.90036 |

[2] | Drezner, Z.; Thisse, J.F.; Wesolowsky, G.O., The minimax-MIN location problem, Journal of regional science, 26, 87-101, (1986) |

[3] | Drezner, Z.; Wesolowsky, G.O., The asymmetric distance location problem, Transportation science, 23, 3, 201-207, (1989) · Zbl 0682.90037 |

[4] | Durier, R.; Michelot, C., Geometrical properties of the Fermat-Weber problem, European journal of operational research, 20, 332-343, (1985) · Zbl 0564.90013 |

[5] | Erlenkotter, D., The general optimal market area model, Annals of operations research, 18, 45-70, (1989) · Zbl 0707.90056 |

[6] | Halpern, J., The location of a center-Median convex combination on an undirected tree, Journal of regional science, 16, 237-245, (1976) |

[7] | Hampel, F.R.; Ronchetti, E.M.; Rousseeuw, P.J.; Stahel, W.A., Robust statistics — the approach based on influence functions, (1986), Wiley New York · Zbl 0593.62027 |

[8] | Hansen, P. (1987), private communication. |

[9] | Hansen, P.; Peeters, D.; Richard, D.; Thisse, J.F., The minisum and minimax lacation problems revisited, Operations research, 33, 1251-1265, (1985) · Zbl 0582.90027 |

[10] | Hansen, P.; Thisse, J.F., Recent advances in continuous location theory, Sistemi urbani, 1, 33-54, (1983) |

[11] | Hodgson, M.J.; Wong, R.T.; Honsaker, J., The p-centroid problem on an inclined plane, Operations research, 35, 2, 221-233, (1987) · Zbl 0635.90029 |

[12] | Horowitz, E.; Sahni, S., Fundamentals of data structures, (1976), Pitman London · Zbl 0408.68003 |

[13] | Horst, R., A general class of branch and bound methods in global optimization with some new approaches for concave minimization, Journal of optimization theory and applications, 51, 271-291, (1986) · Zbl 0581.90073 |

[14] | Karkazis, J.; Papadimitriou, C., A branch and bound algorithm for the location of facilities causing atmospheric pollution, European journal of operational research, 58, 3, 363-373, (1992) · Zbl 0760.90066 |

[15] | Kaufman, L.; Plastria, F., The Weber problem with supply surplus, Belgian journal of operations research, statistics and computer science, 28, 1, 15-31, (1988) · Zbl 0657.90035 |

[16] | Kuhn, H.W., On a pair of dual nonlinear programs, (), 37-54 · Zbl 0183.22804 |

[17] | Love, R.L.; Morris, J.G.; Wesolowsky, G.O., Facilities location: models and methods, (1988), North-Holland Amsterdam · Zbl 0685.90036 |

[18] | Maimon, O., The variance equity measure in locational decision theory, (), 147-160 |

[19] | Plastria, F., Localization in single facility location, European journal of operational research, 18, 215-219, (1984) · Zbl 0546.90031 |

[20] | Plastria, F., Solving general continuous single facility location problems by cutting planes, European journal of operational research, 29, 98-110, (1987) · Zbl 0608.90022 |

[21] | Plastria, F., The minimization of lower subdifferentiable functions under nonlinear constraints: an all feasible cutting plane algorithm, Journal of optimization theory and applications, 57, 3, 463-484, (1988) · Zbl 0621.90079 |

[22] | Plastria, F., On fixed point optimality in asymmetric distance Fermat-Weber problems, () · Zbl 0783.90061 |

[23] | Preparata, F.P.; Shamos, M.I., Computational geometry — an introduction, (1985), Springer-Verlag Berlin · Zbl 0759.68037 |

[24] | Ratschek, H.; Rokne, J., New computer methods for global optimisation, (1988), Ellis Horwood Chichester · Zbl 0648.65049 |

[25] | Tellier, L.N., Points d’attraction, points de repulsion, centre et peripherie, () |

[26] | Tellier, L.N.; Polanski, B., The Weber problem: frequency of different solution types and extension to repulsive forces and dynamic processes, Journal of regional science, 29, 3, 387-405, (1989) |

[27] | Tuy, H.; Horst, R., Convergence and restart in branch and bound algorithms for global optimisation. application to concave minimization and d.c. optimisation problems, Mathematical programming, 41, 2, 161-184, (1988) · Zbl 0651.90063 |

[28] | Ventura, J.A.; Yeralan, S., The minimax center estimation problem for automated roundness inspection, European journal of operational research, 41, 64-72, (1989) · Zbl 0668.90038 |

[29] | Witzgall, C., Optimal location of a central facility: mathematical models and concepts, () |

[30] | Yeralan, S.; Ventura, J.A., Computerized roundness inspection, International journal of production research, 26, 1921-1935, (1988) |

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.