On parallel computing for stochastic optimization models and algorithms

  1. Aldasoro Marcellan, Unai
Zuzendaria:
  1. Gloria Pérez Sainz de Rozas Zuzendaria
  2. María Merino Maestre Zuzendaria

Defentsa unibertsitatea: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 2015(e)ko urtarrila-(a)k 13

Epaimahaia:
  1. Luis Vega González Presidentea
  2. María Araceli Garín Martín Idazkaria
  3. Francisco Saldanha Da Gama Kidea
  4. Laureano Fernando Escudero Bueno Kidea
  5. Elena Fernández Aréizaga Kidea

Mota: Tesia

Teseo: 118397 DIALNET lock_openADDI editor

Laburpena

Esta tesis tiene como objetivo principal la resolución de problemas de optimización bajo incertidumbre a gran escala, mediante la interconexión entre las disciplinas de Optimización estocástica y Computación en paralelo. Se describen algoritmos de descomposición desde la perspectivas de programación matemática y del aprovechamiento de recursos computacionales con el fin de resolver problemas de manera más rápida, de mayores dimensiones o/y obtener mejores resultados que sus técnicas homónimas en serie. Se han desarrollado dos estrategias de paralelización, denotadas como inner y outer. La primera de las cuales, realiza tareas en paralelo dentro de un esquema algorítmico en serie, mientras que la segunda ejecuta de manera simultánea y coordinada varios algoritmos secuenciales. La mayor descomposición del problema original, compartiendo el área de factibilidad, creando fases de sincronización y comunicación entre ejecuciones paralelas o definiendo condiciones iniciales divergentes, han sido claves en la eficacia de los diseños de los algoritmos propuestos. Como resultado, se presentan tanto algoritmos exactos como matheurísticos, que combinan metodologías metaheurísticas y técnicas de programación matemática. Se analiza la escalabilidad de cada algoritmo propuesto, y se consideran varios bancos de problemas de diferentes dimensiones, hasta un máximo de 58 millones de restricciones y 54 millones de variables (de las cuales 15 millones son binarias). La experiencia computacional ha sido principalmente realizada en el cluster ARINA de SGI/IZO-SGIker de la UPV/EHU.