Métodos algebraicos basados en test-sets para optimización lineal entera multiobjetivo

Abstract

En esta memoria se presenta un nuevo método algebraico para resolver de forma exacta problemas de programación multiobjetivo lineal entera para cualquier número de objetivos. Dicho método está basado en el uso de los test-sets asociados a los problemas lineales enteros que surgen con el método tradicional de las restricciones. En el capítulo 1 mostramos una breve introducción a los problemas multiobjetivo y a los conceptos principales que aparecen en su estudio, así como algunos métodos clásicos para resolverlos. En el capítulo 2 recordamos los resultados algebraicos que fundamentan el ingrediente algebraico básico en el que se basa nuestro método, los test-sets asociados a un problema lineal entero m__nfcx; s:a:Ax = b; x 2 Nng, que son validos para todo b. Esta característica hace natural el uso de los test-sets para aplicar el método clásico de las restricciones. Los test-sets serán calculados con bases de Grobner respecto de órdenes que, elegidos convenientemente, producen ventajas añadidas. En el capitulo 3 presentamos los resultados teóricos que sustentan el algoritmo para el caso biobjetivo lineal entero, que calcula todos los puntos no dominados sin resolver ningún problema de un sólo objetivo innecesario y sin producir soluciones debilmente recientes. Además, mostramos una ventaja adicional del uso de los test-sets: en algunas familias de problemas pueden ser calculados teóricamente a priori. Hacemos precisamente esto con un problema de la literatura, el problema BBV. Terminamos con tablas de resultados computacionales con especial interés en el problema de la mochila no acotada. En el capítulo 4 tratamos el caso de cualquier número de objetivos. Conseguimos un algoritmo que produce todos los puntos no dominados y sólo puntos no dominados, pero sin poder asegurar que no se resolver algún problema de un sólo objetivo innecesario al aplicar el método de las restricciones. Resolvemos un problema de la literatura de tres objetivos en sistemas serie-paralelo y al final de este capítulo mostramos resultados computacionales al tratar el problema de la mochila no acotada para 3, 4 y 5 objetivos.