Artículo
A fresh view on the Discrete Ordered Median Problem based on partial monotonicity
Autor/es | Marín, Alfredo
Ponce López, Diego Puerto Albandoz, Justo |
Departamento | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Fecha de publicación | 2020-04-14 |
Fecha de depósito | 2024-09-24 |
Publicado en |
|
Resumen | This paper presents new results for the Discrete Ordered Median Problem (DOMP). It exploits properties of k-sum optimization to derive specific formulations for the monotone DOMP (MDOMP), that arises when the λ weights are ... This paper presents new results for the Discrete Ordered Median Problem (DOMP). It exploits properties of k-sum optimization to derive specific formulations for the monotone DOMP (MDOMP), that arises when the λ weights are non-decreasing monotone, and new formulations for the general non-monotone DOMP. The main idea in our approach is to express ordered weighted averages as telescopic sums whose terms are k-sums, with positive and negative coefficients. Formulations of k-sums with positive coefficients derive from the linear programming representations obtained by Ogryczack and Tamir (2003) and Blanco, Ali, and Puerto (2014). Valid formulations for k-sums with negative coefficients are more elaborated and we present 4 different approaches, all of them based on mixed integer programming formulations. An extensive computational experience based on a collection of well-known instances shows the usefulness of the new formulations to solve difficult problems such as trimmed and anti-trimmed mean. |
Cita | Marín, A., Ponce López, D. y Puerto Albandoz, J. (2020). A fresh view on the Discrete Ordered Median Problem based on partial monotonicity. European Journal of Operational Research, 286 (3), 839-848. https://doi.org/10.1016/j.ejor.2020.04.023. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A fresh view on the Discrete ... | 449.4Kb | [PDF] | Ver/ | |