Integralidad de poliedros en problemas de PLE: perfecci´on y persistencia

ESCALANTE, MARIANA SILVINA

Bahia Blanca

Congreso; XVII Congreso Dr. A. Monteiro; 2023

Universidad Nacional del Sur

Sobre la construcción de estructuras en grafos asociadas a la integralidad de poliedros presentes en ciertos problemas de programación entera: perfección y persistencia.El objetivo de esta charla es la presentación de dos enfoques distintos para el abordaje deproblemas de optimización modelados como problemas de programación entera.En el primero de ellos se considera la familia de problemas de empaquetamiento (k-packingfunction problem) sobre un grafo. En el caso en que la matriz de vecindades cerradas del grafosea una matriz perfecta, el poliedro región factible de la relajación lineal de estos problemas esentero. En este caso, el problema entero se resuelve via programación lineal para cualquier función objetivo. Esto motiva el estudio de la familia de grafos con matriz de vecindades perfecta.El aporte principal que realizamos es una caracterización de esta familia de grafos a partir deestructuras prohibidas.En un segundo enfoque de problemas de programación entera está asociado al estudio de lapropiedad poliedral de persistencia. Esta propiedad fue estudiada sobre el problema de maximoconjunto estable en un grafo y permite el diseño de métodos iterativos de resolución de problemas enteros 0-1. Se mostró en otros trabajos que la única reljación no trivial del politopo de losconjuntos estables que la posee es la relajación por arcos. Dada esta propiedad, presentamosuna variante de la misma (1-persistencia) y analizamos su validez para la relajación clique delproblema de los conjuntos estables. En esta línea actual de trabajo apuntamos a caracterizar estafamilia de grafos y extender los resultados a otro tipo de relajaciones del mismo.