Optimización Combinatoria

Dr. Hernán Abeledo

abeledo@gwu.edu, habeledo@dc.uba.ar

Profesor Asociado, George Washington University.

Profesor Visitante, Departamento de Computación, UBA.

Materia Optativa para la Licenciatura y Doctorado en Ciencias de la Computación

(abierta para alumnos de otras carreras).

 

Modalidad de la materia: La materia tendrá 6 horas de clases teórico-prácticas semanales.

Duración del curso: 9 semanas (semana del 10 de Marzo -- semana del 12 deMayo)

Horario: Martes y Viernes 16:00 - 19:00 hs Aula 12 o 13 - Pabellon I).

Correlativas: Algoritmos y Estructuras de Datos III o Métodos Numéricos o Investigación Operativa (a confirmar por Codep)

Evaluación: Trabajos prácticos, Promoción o Final.

Puntaje: 2 Puntos

Objetivos de la materia:

El objetivo de esta materia es el estudio de la optimización combinatoria desde una perspectiva poliedral, utilizando los métodos y teoría de la programación lineal y lineal-entera. El curso incluye una revisión de los resultados teóricos esenciales de la programación lineal.

La optimización combinatoria estudia el modelado y solución algorítmica de problemas donde se busca maximizar (o minimizar) una función de varias variables definidas sobre un conjunto discreto. Esta disciplina tiene numerosas aplicaciones a problemas que se presentan en la industria, logística, ciencias, ingenierías y en la administración de organizaciones. Como ejemplos podemos mencionar, entre otros, el ruteo y carga de vehículos en redes de distribución, el diseño de redes de telecomunicación, la planificación de la producción, la selección de carteras financieras, la asignación de tareas a procesadores, el análisis de estructuras moleculares, las subastas de frecuencias para radiotransmisión, la asignación de tripulaciones en líneas aéreas, la planificación de la generación de electricidad y la distribución de ambulancias en una región para asegurar un cierto nivel de servicio a su población. La gran variedad de posibles aplicaciones es una fuente constante de problemas nuevos para la investigación en este área.

En la optimización combinatoria confluyen la matemática discreta, la teoría de algoritmos, y la programación lineal y lineal-entera. Un problema de programación lineal consiste en hallar el valor óptimo de una función objetivo lineal cuyas variables están sujetas a restricciones lineales. Si además se exige que las variables tomen valores enteros, entonces se tiene un problema de programación lineal-entera. Varios problemas de Optimización Combinatoria pueden ser resueltos en tiempo polinomial utilizando los métodos y teoría de la programación lineal. En el caso de los problemas NP-Completos, los métodos más eficaces en la actualidad para encontrar una solución exacta a muchos de estos problemas utilizan, típicamente, la programación lineal-entera.

Programa:

Introducción a la Optimización Combinatoria y a la Programación Entera. Ejemplos de modelos y aplicaciones: problemas de flujo en redes, problema de transporte, camino mínimo en un grafo, matching, cubrimiento, problema del viajante de comercio, problema de la mochila.

Revisión de Programación Lineal. Problema dual. Lema de Farkas. Teorema de dualidad. Teorema de Holgura Complementaria.

Teoría de Poliedros. Desigualdades válidas. Puntos extremos, caras y facetas. Cápsula convexa. Poliedros enteros. Matrices totalmente unimodulares y matrices unimodulares. Separación y optimización. Complejidad computacional.

Formulación y solución de problemas en grafos y redes como problemas de programación lineal. Camino mínimo, flujo máximo, problema de transporte, matching. Problema de los casamientos estables. Problemas en grafos de moleculas de bencenoides.

Problemas de Programación Entera. Buenas y malas formulaciones Desigualdades válidas fuertes. Relajaciones. Problemas duales.

Algoritmos de resolución de un problema lineal entero. Métodos de planos de corte. Métodos Branch and Bound. Métodos Branch and Cut.

Estudio de la cápsula convexa para algunos problemas de programación lineal entera: mochila, viajante de comercio.

 

Bibliografía

  1. Bazaraa, M., Jarvis, J., Sherali, Linear Programming and Network Flows, John Wiley &.Sons, 1990.
  2. Chvatal, V., Linear Programming, Freeman, 1983.
  3. Cook, W., Cunningham,W, Pulleyblank, Schrijver, A., Combinatorial Optimization, John Wiley &.Sons, 1998.
  4. Hillier,F., Lieberman,G., Introduction to Operations Research,7ma ed., McGraw-Hill, 2000.
  5. Nemhauser,G., Wosley,L., Integer and Combinatorial Optimization, John Wiley &.Sons, 1988.
  6. Papadimitriou,C., Steiglitz,K., Combinatorial Optimization, Dover, 1998.
  7. Schrijver,A.Theory of Linear and Integer Programming, John Wiley & Sons, 1986.
  8. Wolsey,L., Integer Programming, John Wiley &.Sons, 1998.

 

Practicas

  • Practica 1
  •  

    Apuntes

  • Apunte 1: Introduccion
  • Apunte 2: Metodo Simplex
  •  

    Apuntes "Discrete Optimization" (IE418), por Ted Ralph (www.lehigh.edu/~tkr2/teaching/ie418).

  • Lecture 1
  • Lecture 2
  •  

    Apuntes "Advanced Operations Research Techniques" (IE316), por Ted Ralph (www.lehigh.edu/~tkr2/teaching/ie316).

  • Lecture 1
  • Lecture 2
  • Lecture 3
  • Lecture 4
  • Lecture 5