Sesión Análisis Numérico y Optimización

Diciembre 14, 12:00 ~ 12:20

An exact copositive programming formulation for the Discrete Ordered Median Problem

Puerto, Justo

This paper presents a first exact continuous, linear, conic formulation for the Discrete Ordered Median Problem (DOMP). Starting from a binary, quadratic formulation in the original space of location and allocation variables that are common in Location Analysis (L.A.), we prove that there exists a transformation of that formulation, using the same space of variables, that allows to cast DOMP as a continuous linear problem in the space of completely positive matrices. This is the first positive result that states equivalence between the family of continuous convex problems and some hard problems in L.A. The result is of theoretical interest because allows to share the tools from continuous optimization to shed new light into the difficult combinatorial structure of the class of ordered median problems. \noindent \textbf{Keywords.} Discrete ordered median problem; exact copositive reformulation; conic linear programming. \medskip \bibliographystyle{plainnat} \begin{thebibliography}{13} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\texttt{#1}} \expandafter\ifx\csname urlstyle\endcsname\relax \providecommand{\doi}[1]{doi: #1}\else \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi \bibitem[Blanco et~al.(2014)Blanco, Ali, and Puerto]{BHP2014} V.~Blanco, S.~El Haj~Ben Ali, and J.~Puerto. \newblock Revisiting several problems and algorithms in continuous location wih $l_\tau-$norm. \newblock \emph{Computational Optimization and Applications}, 58\penalty0 (3):\penalty0 563--595, 2014. \bibitem[Boland et~al.(2006)Boland, Dom{í}nguez-Mar{í}n, Nickel, and Puerto]{Boland2006} N.~Boland, P.~Dom{í}nguez-Mar{í}n, S.~Nickel, and J.~Puerto. \newblock Exact procedures for solving the discrete ordered median problem. \newblock \emph{Computers \& Operations Research}, 33\penalty0 (11):\penalty0 3270--3300, 2006. \newblock ISSN 0305-0548. \bibitem[Bomze(2012)]{Bomze12} I.~M. Bomze. \newblock Copositive optimization - recent developments and applications. \newblock \emph{European Journal of Operational Research}, 216\penalty0 (3):\penalty0 509--520, 2012. \newblock \doi{10.1016/j.ejor.2011.04.026}. \newblock URL \url{https:/doi.org/10.1016/j.ejor.2011.04.026}. \bibitem[Nickel and Puerto(2005)]{Nickel2005} S.~Nickel and J.~Puerto. \newblock \emph{Location Theory: A Unified Approach.} \newblock Springer Verlag, 2005. \end{thebibliography}

Autores: Puerto, Justo.