On the multisource hyperplanes location problem to fitting set of points

Blanco, V. ; Japón, A. ; Ponce, D. ; Puerto, J.

Resumen: 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.

Idioma: Inglés

DOI: 10.1016/j.cor.2020.105124

Año: 2021

Publicado en: Computers and Operations Research 128 (2021), 105124 [15 pp]
ISSN: 0305-0548

Factor impacto JCR: 5.159 (2021)

Categ. JCR: OPERATIONS RESEARCH & MANAGEMENT SCIENCE rank: 20 / 87 = 0.23 (2021) - Q1 - T1
Categ. JCR: COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS rank: 35 / 112 = 0.312 (2021) - Q2 - T1
Categ. JCR: ENGINEERING, INDUSTRIAL rank: 19 / 50 = 0.38 (2021) - Q2 - T2

Factor impacto CITESCORE: 8.3 - Computer Science (Q1) - Mathematics (Q1) - Decision Sciences (Q1)

Factor impacto SCIMAGO: 1.855 - Management Science and Operations Research (Q1) - Computer Science (miscellaneous) (Q1)

Financiación: info:eu-repo/grantAgreement/ES/FEDER/CEI-3-FQM331
Financiación: info:eu-repo/grantAgreement/ES/FEDER/US-1256951
Financiación: info:eu-repo/grantAgreement/ES/MEC-FEDER/MTM2016-74983-C02-01
Financiación: info:eu-repo/grantAgreement/ES/MEC-FEDER/MTM2016-74983-C02-02

Tipo y forma: Article (PostPrint)