Optimización combinatoria

La optimización combinatoria es la búsqueda de los valores de ciertos elementos (variables) que optimicen una función objetivo definida sujeta a un conjunto de restricciones. Dado que son varios los elementos que se buscan, la combinación de diferentes valores en cada variable forman conjunto de soluciones posibles.

Cuando el espacio de búsqueda es "infinito" se aplican diferentes técnicas y algoritmos que ayuden a encontrar una buena solución en vez de la mejor (la que optimiza la función) ya que el costo (tiempo) de realizar la búsqueda de la mejor puede ser demasiado. Entonces se evalúa el costo-beneficio del problema para aceptar una buena solución encontrada.

Bibliografía básica: 

  • Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization : Algorithms and Complexity

  • Bernhard Korte, Jens Vygen; Combinatorial Optimization: Theory and algorithms