Una gran variedad de problemas de optimización provenientes de áreas de aplicación muy diversas y cuya resolución es muy compleja desde el punto de vista computacional - los denominados problemas NP -completos- pueden ser modelados a partir de la Programación Lineal Entera. En particular, la mayor parte de los problemas de Optimización Combinatoria admiten modelos en esta familia.
En los últimos años la modelización como programas lineales enteros ha resultado ser la herramienta más eficiente para la realización exacta de grandes instancias de estos problemas. Su buen rendimiento computacional se basa fundamentalmente en las buenas cotas que brinda la Programación Lineal (para la cual existen implementaciones computacionales muy eficientes de fácil acceso, permitiendo considerar su uso como una rutina) y el estudio teórico de la estructura poliedral del modelo.
En esta línea de trabajo se conjugan creativamente la teoría de grafos, el álgebra lineal y la teoría de poliedros.

1.- Formulaciones: ¿qué es un programa entero?, explosión combinatoria; formulaciones enteras y entero-mixtas, formulaciones alternativas; formulaciones buenas e ideales.
2.- Optimalidad, relajación y cotas: optimalidad y relajación; relajaciones de la Programación Lineal;

relajaciones combinatorias; relajación Lagrangeana; dualidad; cotas primales.
3.- Problemas \"bien resueltos\": propiedades de los problemas sencillos; matrices totalmente unimodulares; problema de flujo de mínimo costo; casos especiales, camino más corto y máximo flujo; árboles óptimos; reformulación de Bender.
4.- Emparejamientos y asignaciones: caminos aumentantes y optimalidad; máximo emparejamiento en grafos bipartitos; el problema de asignación.
5.- Complejidad y reducción de problemas: complejidad; problemas de decisión y las clases P y NP; reducciones polinomiales y la clase NPC; consecuencias de P = NP ó PNP; optimización y separación.
6.- Ramificación y cota (branch and bound): divide y conquistarás; enumeración implícita; ramificación y coa basada en Programación Lineal, usando un sistema de ramificación y cota; preprocesamiento.
7.- Algoritmos de planos de corte: desigualdades válidas; algoritmos de planos de corte y reformulaciones automáticas; planos de corte Gomory; cortes enteros mixtos.
8.- Desigualdades válidas profundas: denominación; poliedros, caras y facetas; desigualdades de mochila; problema de separación; desigualdades mixtas 0-1; separación para restricciones generalizadas de sub-recorridos; ramificación y corte.

---

Examen Final.