On parallel computing for stochastic optimization models and algorithms

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

Defence university: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 13 January 2015

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

Type: Thesis

Teseo: 118397 DIALNET lock_openADDI editor

Abstract

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.