Obtención de facetas de poliedros asociados a problemas de empaquetamiento

Résumé

El objetivo general de la memoria es profundizar en el estudio políedrico de los problemas de empaquetamiento, El problema de empaquetemiento es el problema de maximizar un función objetivo lineal sujeta a un conjunto de restricciones lineales con termino independiente unitario y variables binarias. El estudio poliédico consiste basicamente en la identificacion de desigualdades validas o, preferiblemente, de facetas. Por otro lado, el estudio poliedrico es un procedimiento para tratar problemas enteros en general: no es exlusivo para los problemas de empaquetamiento. Varios motivos para abordar el estudio de desigualdades válidas del problema de empaquetamiento son: 1. Los métodos de ramificación y corte son herramientas muy usadas y útiles para resolver problemas enteros en general. 2. Algunos problemas enteros o mixtos contienen restricciones con coeficientes 0-1 exclusivamente. 3. Algunos procesadores de problemas enteros generan de manera automática restricciones con coeficientes binarios como, por ejemplo, cotas. La memoria se propone cuatro objetivos específicos: 1.Obtener procedimientos que transformen facetas de poliedros en facetas de otros poliedros. Por un lado se busca transformar facetas de poliedros en otros de mayor dimensión, lo que se conoce con el nombre de levantamientos, y por otro transformar las originales en otras de poliedros de menor dimensión, lo que se dice proyectar la faceta. 2. Identificar familias de poliedros de las que se conozcan familias de facetas. Aprovechando los procedimientos transformadores se pueden exportar las facetas de poliedros pequeños con buenas propiedades a toros más complejos. 3. Aplicar todo lo anterior para mejorar la descripción poliédrica actual de dos problemas conocidos de localización discreta que se formulan como problemas de empaquetamiento: los llamados "problema de localización de plantas simple" y "problema de localización de plantas con capa