×

On the multisource hyperplanes location problem to fitting set of points. (English) Zbl 1510.90169

Summary: In this paper we study the problem of locating a given number of hyperplanes minimizing an objective function of the closest distances from a set of points. We propose a general framework for the problem in which norm-based distances between points and hyperplanes are aggregated by means of ordered median functions. A compact Mixed Integer Linear (or Non Linear) programming formulation is presented for the problem and also an extended set partitioning formulation with a huge number of variables is derived. We develop a column generation procedure embedded within a branch-and-price algorithm for solving the problem by adequately performing its preprocessing, pricing and branching. We also analyze geometrically the optimal solutions of the problem, deriving properties which are exploited to generate initial solutions for the proposed algorithms. Finally, the results of an extensive computational experience are reported. The issue of scalability is also addressed showing theoretical upper bounds on the errors assumed by replacing the original datasets by aggregated versions.

MSC:

90B85 Continuous location
90C11 Mixed integer programming

Software:

SCIP; CRIO; Algorithm 39
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Balas, E.; Padberg, M. W., Set partitioning: a survey, SIAM Review, 18, 4, 710-760 (1976) · Zbl 0347.90064
[2] Bertsimas, D.; Shioda, R., Classification and regression via integer optimization, Operations Research, 55, 2, 252-271 (2007) · Zbl 1167.90593
[3] Blanco, V.; Japón, A.; Puerto, J., Optimal arrangements of hyperplanes for svm-based multiclass classification, Advances in Data Analysis and Classification, 14, 175-199 (2020) · Zbl 1474.62213
[4] Blanco, V.; Puerto, J.; El-Haj Ben-Ali, S., Revisiting several problems and algorithms in continuous location with \(\ell_\tau \)-norms, Computational Optimization and Applications, 58, 3, 563-595 (2014) · Zbl 1297.90073
[5] Blanco, V.; Puerto, J.; El-Haj Ben-Ali, S., Continuous multifacility ordered median location problems, European Journal of Operational Research, 250, 1, 56-64 (2016) · Zbl 1346.90527
[6] Blanco, V., Puerto, J., Rodríguez-Chía, A.M., 2020b. On l_p support vector machines and multidimensional kernels. Journal of Machine Learning Research 21(14), 1-29. · Zbl 1498.68224
[7] Blanco, V.; Puerto, J.; Salmerón, R., Locating hyperplanes to fitting set of points: A general framework, Computers & Operations Research, 95, 172-193 (2018) · Zbl 1458.90467
[8] Bradley, P. S.; Mangasarian, O. L., K-plane clustering, Journal of Global Optimization, 16, 1, 23-32 (2000) · Zbl 0990.90135
[9] Brimberg, J.; Juel, H.; Schöbel, A., Linear facility location in three dimensions—models and solution methods, Operations Research, 50, 6, 1050-1057 (2002) · Zbl 1163.90616
[10] Brimberg, J.; Juel, H.; Schöbel, A., Properties of three-dimensional median line location models, Annals of Operations Research, 122, 1-4, 71-85 (2003) · Zbl 1038.90047
[11] Carbonneau, R. A.; Caporossi, G.; Hansen, P., Globally optimal clusterwise regression by column generation enhanced with heuristics, sequencing and ending subset optimization, Journal of Classifications, 31, 2, 219-241 (2014) · Zbl 1360.62318
[12] Cortes, C.; Vapnik, V., Support-vector networks, Machine Learning, 20, 3, 273-297 (1995) · Zbl 0831.68098
[13] Current, J. R.; Schilling, D. A., Elimination of source a and b errors in p-median location problems, Geographical Analysis, 19, 2, 95-110 (1987)
[14] Current, J. R.; Schilling, D. A., Analysis of errors due to demand data aggregation in the set covering and maximal covering location problems, Geographical Analysis, 22, 2, 116-126 (1990)
[15] Eilon, S.; Watson-Gandy, C. D.T.; Christofides, N., Distribution Management: Mathematical Modelling and Practical Analysis (1971), Griffin: Griffin London
[16] Espejo, I.; Rodríguez-Chía, A. M., Simultaneous location of a service facility and a rapid transit line, Computers & Operations Research, 38, 2, 525-538 (2011) · Zbl 1231.90274
[17] Gauss, C.F., 1809. Theoria motus corporum coelestium in sectionibus conicis solem ambientium, volume 7. Perthes et Besser. · Zbl 1234.01016
[18] Geoffrion, A., Objective function approximations in mathematical programming, Mathematical Programming, 13, 23-39 (1977) · Zbl 0356.90062
[19] Gitman, I., Chen, J., Lei, E., Dubrawski, A., 2018. Novel prediction techniques based on clusterwise linear regression. arXiv preprint arXiv:1804.10742.
[20] Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Lübbecke, M.E., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J. (2018). The SCIP Optimization Suite 6.0. Technical report, Optimization Online.
[21] Hennig, C., Models and methods for clusterwise linear regression, (Classification in the Information Age (1999), Springer), 179-187
[22] Mangasarian, O. L., Arbitrary-norm separating plane, Operations Research Letters, 24, 1-2, 15-23 (1999) · Zbl 1028.90037
[23] Martini, H.; Schöbel, A., Median hyperplanes in normed spaces—a survey, Discrete Applied Mathematics, 89, 1-3, 181-195 (1998) · Zbl 0921.90109
[24] Martini, H.; Schöbel, A., Median and center hyperplanes in minkowski spaces—a unified approach, Discrete Mathematics, 241, 1-3, 407-426 (2001) · Zbl 1010.51002
[25] McGee, V. E.; Carleton, W. T., Piecewise regression, Journal of the American Statistical Association, 65, 331, 1109-1124 (1970)
[26] Ogryczak, W.; Tamir, A., Minimizing the sum of the k largest functions in linear time, Information Processing Letters, 85, 3, 117-122 (2003) · Zbl 1050.68155
[27] Park, Y. W.; Jiang, Y.; Klabjan, D.; Williams, L., Algorithms for generalized clusterwise linear regression, INFORMS Journal on Computing, 29, 2, 301-317 (2017) · Zbl 1528.62036
[28] Plastria, F.; Carrizosa, E., Gauge distances and median hyperplanes, Journal of Optimization Theory and Applications, 110, 1, 173-182 (2001) · Zbl 1039.90036
[29] Quandt, R. E., The estimation of the parameters of a linear regression system obeying two separate regimes, Journal of the American Statistical Association, 53, 284, 873-880 (1958) · Zbl 0116.37304
[30] Ryan, D.M., Foster, A., 1981. An integer programming approach to scheduling. In: Wren, A. (Ed.), Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling. North-Holland, Amsterdan, 269-280.
[31] Schöbel, A., Locating Lines and Hyperplanes: Theory and Algorithms, vol. 25 (1999), Springer Science & Business Media · Zbl 0918.90102
[32] Schöbel, A., Anchored hyperplane location problems, Discrete and Computational Geometry, 29, 2, 229-238 (2003) · Zbl 1032.90017
[33] Schöbel, A., 2015. Location of dimensional facilities in a continuous space. In: Location Science, 135-175.
[34] Späth, H., A fast algorithm for clusterwise linear regression, Computing, 29, 2, 175-181 (1982) · Zbl 0485.65030
[35] Vapnik, V., The Nature of Statistical Learning Theory (2013), Springer science & business media · Zbl 0934.62009
[36] Weber, A., Ueber den standort der industrien, vol. 1 (1909), Verlag J.C.B.Mohr: Verlag J.C.B.Mohr Tübingen
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.