Poliedros asociados a problemas de programación lineal entera mixta

Dra. Mariana Escalante
mariana@fceia.unr.edu.ar

La Optimización Combinatoria permite modelar una gran variedad de problemas provenientes de las aplicaciones, los cuales pueden ser formulados como hallar el máximo (mínimo) de una función lineal con restricciones lineales (PL), donde algunas variables pueden ser enteras (PLEM o PLE). Las técnicas clásicas para su resolución consisten, en general, en la obtención de aproximaciones poliedrales sucesivas que contienen a las soluciones del problema. Sin embargo, el número de pasos puede ser muy grande y no se conoce una implementación algorítmica eficiente en general.
El proyecto está basado en el estudio de los siguientes problemas de PLE:

TEMA 1: Problema del máximo conjunto estable en un grafo: enfoque lift-and-project.
Una línea de trabajo para la búsqueda del máximo de una función lineal sobre el conjunto de los vectores característicos de los conjuntos estables en un grafo G, es optimizar sobre su cápsula convexa STAB(G), cuya descripción por desigualdades lineales no se conoce para grafos generales. Una forma de hallar relajaciones cada vez más ajustadas a STAB(G) es aplicar operadores lift-and-project sobre la relajación por arcos, FRAC(G). Dentro de estos operadores utilizaremos los definidos en Lovász y Schrijver (1991), N0, N y N+. Permanece abierta la conjetura de Lipták y Tunçel (2003) sobre la igualdad de los rangos de los operadores N0 y N aplicados sobre FRAC(G).

TEMA 2: Problema del coloreo por vértices con adyacencias mínimas: estudio poliedral.
El problema de asignación de colores a los vértices de un grafo de manera que se minimice la cantidad de vértices vecinos que reciben colores adyacentes, proviene de la asignación de frecuencias en redes de telefonía celular. Este problema se comenzó a estudiar desde el punto de vista poliedral en Delle Donne y Marenco (2011), donde se hallaron algunas familias de desigualdades válidas que definen facetas. Estas desigualdades no son suficientes para describir el poliedro cápsula convexa de las soluciones factibles aún en pequeñas instancias, dejando abierta la posibilidad de continuar su estudio y hallar nuevas familias infinitas de desigualdades válidas y condiciones para que las mismas describan el poliedro en estudio.

TEMA 3: Problema del k-empaquetamiento limitado en un grafo: estudio poliedral.
Un conjunto dominante en un grafo G es un conjunto de nodos con intersección no vacía con toda vecindad cerrada. Este concepto fue generalizado en Gallant, Gunther, Hartnell y Rall (2008): una k-upla dominante es un conjunto de nodos con al menos k elementos en común con toda vecindad cerrada. En ciertas aplicaciones interesa encontrar el tamaño de una k-upla dominante de mínima cardinalidad. El problema de un k-empaquetamiento limitado de máxima cardinalidad generaliza al clásico problema de dominación en un grafo (donde k=1). Permanece abierta la caracterización del poliedro cápsula convexa de las soluciones enteras factibles del problema para familias de grafos más generales que los ciclos, como los grafos cactus, que se obtienen como 1-suma de ciclos y aristas.