EL PROBLEMA DE LA P-MEDIANA: DEFINICIÓN Y MODELOS DE RESOLUCIÓN

Abstract

ESTE TRABAJO DE FIN DE GRADO ESTUDIA EL PROBLEMA DE LA P-MEDIANA EN REDES DESDE UNA PERSPECTIVA TEóRICO-COMPUTACIONAL. PARTIENDO DE LA FORMULACIóN CONTINUA ORIGINAL DE HAKIMI, DONDE LAS INSTALACIONES PUEDEN UBICARSE EN CUALQUIER PUNTO DE LA RED, SE JUSTIFICA RIGUROSAMENTE LA DISCRETIZACIóN DEL MODELO: SE DEMUESTRA QUE SIEMPRE EXISTE UNA SOLUCIóN óPTIMA CON LAS MEDIANAS SITUADAS EN VéRTICES, LO QUE PERMITE TRABAJAR CON UN CONJUNTO FINITO DE CANDIDATOS. SOBRE ESTE MARCO SE INTRODUCEN FORMULACIONES DE PROGRAMACIóN LINEAL ENTERA BINARIA, QUE SIRVEN DE BASE PARA UN SOLUCIONADOR EXACTO IMPLEMENTADO EN PYTHON MEDIANTE PULP. DESDE EL PUNTO DE VISTA DE LA COMPLEJIDAD, SE ENCUADRA EL PROBLEMA DENTRO DE LAS CLASES P Y NP Y SE ESTABLECE SU NP-DIFICULTAD INCLUSO EN GRAFOS PLANARES DE GRADO MáXIMO TRES, CON LONGITUDES Y DEMANDAS UNITARIAS, MEDIANTE REDUCCIONES POLINóMICAS DESDE PROBLEMAS CLáSICOS DE TEORíA DE GRAFOS. ESTE RESULTADO MOTIVA LA NECESIDAD DE RECURRIR A TéCNICAS ESPECíFICAS DE OPTIMIZACIóN ENTERA Y A ALGORITMOS HEURíSTICOS CUANDO EL TAMAñO DE LAS INSTANCIAS CRECE. EN EL PLANO COMPUTACIONAL SE IMPLEMENTA Y COMPARA UN CONJUNTO VARIADO DE MéTODOS DE RESOLUCIóN: HEURíSTICAS CLáSICAS DE CONSTRUCCIóN Y DESCARTE VORAZ, PROCEDIMIENTOS DE MEJORA LOCAL POR INTERCAMBIOS 1-SWAP Y SU VERSIóN PARALELA, ASí COMO DOS METAHEURíSTICAS REPRESENTATIVAS, GRASP Y VNS. LOS EXPERIMENTOS NUMéRICOS SOBRE INSTANCIAS DE TAMAñO CRECIENTE MUESTRAN UN PATRóN CLARO DE COMPROMISO ENTRE EL TIEMPO DE EJECUCIóN Y LA CALIDAD DE LA SOLUCIóN: LOS MéTODOS CONSTRUCTIVOS SON EXTREMADAMENTE RáPIDOS PERO MENOS PRECISOS, MIENTRAS QUE LAS HEURíSTICAS DE INTERCAMBIO Y LAS METAHEURíSTICAS LOGRAN SOLUCIONES MUY CERCANAS AL óPTIMO A COSTA DE TIEMPOS DE CóMPUTO MAYORES. EN CONJUNTO, EL TRABAJO PROPORCIONA UNA VISIóN INTEGRADA QUE CONECTA LA TEORíA DE GRAFOS, LA COMPLEJIDAD COMPUTACIONAL Y EL DISEñO DE ALGORITMOS PARA EL PROBLEMA DE LA P-MEDIANA EN REDES.