Enhancing performance on combinatorial optimization algorithms
Francisco Cruz Mencía · 2018
L'optimitzacio combinatoria es un tipus especific d'optimitzacio matematica on el domini de les variables es discret. Aquest tipus de problemes d'optimitzacio tenen una gran aplicabilitat degut a la seva capacitat d'optimitzacio sobre objectes unitaris i no divisibles. Mes enlla dels algoritmes generics, la comunitat investigadora es molt activa proposant algorismes capacos d'abordar problemes d'optimitzacio combinatoria per a problemes especifics. L'objectiu d'aquesta tesi es investigar com ampliar l'aplicabilitat d'algorismes d'optimitzacio combinatoria que exploten l'estructura dels problemes a resoldre. Ho fem des de la perspectiva del maquinari d'una computadora, perseguint l'explotacio total dels recursos computacionals que ofereix el maquinari actual. Per assolir generalitat treballem amb tres problemes diferents. Primer abordem el problema de generacio d'estructures de la coalicio (CSGP). Trobem que l'algorisme d'ultima generacio es IDP. Proposem un algoritme optimitzat i paral·lel capac de resoldre el CSGP. Aconseguim aixo definint un nou metode per dur a terme l'operacio mes critica -Splitting-, aixi com definint un nou metode per dividir l'operacio de l'algoritme en els diferent subprocessos. A continuacio, estudiem el problema de determinacio del guanyador (WDP) per a les subhastes combinades (CA). Trobem que l'escalabilitat dels solucionadors d'avantguarda es limitada. Mes concretament, mostrem com millorar la resolucio de resultats de relaxacio LP per al WDP en subhastes combinables de gran escala mitjancant l'aplicacio de l'algoritme AD³. A continuacio, contribuim amb una versio optimitzada d'AD³ que tambe es pot executar en un escenari paral·lel de memoria compartida. Finalment, estudiem l'aplicacio de AD³ per resoldre les relaxacions LP d'un problema mes exigent de la computacionalment: El problema de la predicio de cadenes laterals (SCP). Presentem una manera optimitzada de resoldre l'operacio mes critica, la resol·lucio d'un problema quadratic per a un factor arbitrari. En tots els casos proposem algoritmes optimitzats que es poden escalar de forma paral·lela i que milloren notablement l'estat de la tecnica. Tres ordres de magnitud a IDP, i un ordre de magnitud a AD³. L'objectiu final d'aquest treball es demostrar com un disseny algorisme conscient de maquinari pot conduir a millores de rendiment significatives. Mostrem estrategies exportables a algorismes d'optimitzacio combinatoria similars. Aquestes estrategies ajudaran al dissenyador d'algorismes a assolir mes eficiencia en les CPU modernes.