Optimización combinatoria

Optimización combinatoria

La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.

Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++,en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz.

Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes.

Contenido

Definición formal

Una instancia de un problema de optimización combinatoria puede ser descrito formalmente como una tupla (X,P,Y,f,extr) donde

  • X es el espacio de soluciones (en el cual f y P están definidos)
  • P es la factibilidad predicado.
  • Y es el conjunto de soluciones factibles.
  • f es la función objetivo.
  • extr es el extremo (normalmente min o max).

Ejemplo de problemas

Métodos

Los métodos de búsqueda heurísticos (algoritmos metaheuristicos) como los listados abajo han sido usado para resolver problemas de este tipo.

Véase también

  • Optimización discreta
  • Algoritmos de búsqueda
  • Evolución Diferencial

Referencias

  • William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.
  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
  • Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Optimización — puede refereirse a: En matemáticas: Optimización (matemática), el proceso de encontrar los mínimos y máximos de una función. Algunas de sus ramas son: Optimización combinatoria Optimización multiobjetivo Optimización de topología multifase, una… …   Wikipedia Español

  • Espacio de búsqueda — Saltar a navegación, búsqueda Ejemplo de espacio de búsqueda. Gráfica de una función con múltiples óptimos locales en 2 dimensiones En optimización, espacio de búsqueda se refiere al dominio de la función a ser optimizada. En el caso de los… …   Wikipedia Español

  • Metaheurística — Una metaheurística es un método heurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de una manera que se espera eficiente. Normalmente,… …   Wikipedia Español

  • Problema del viajante — Saltar a navegación, búsqueda Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida? Contenido …   Wikipedia Español

  • Geometría discreta — Una colección de círculos y el correspondiente grafo de disco unitario La geometría discreta y la geometría combinatoria son ramas de la geometría que estudian las propiedades combinatorias de objetos geométricos discretos. La mayoría de las… …   Wikipedia Español

  • Richard Karp — Saltar a navegación, búsqueda Richard Karp Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el …   Wikipedia Español

  • Jack Edmonds — Jack R. Edmonds (n. 1934) es un matemático canadiense, considerado uno de los más importantes contribuyentes al campo de la optimización combinatoria y recibió en 1985 el John von Neumann Theory Prize. Realizó sus estudios en la Universidad… …   Wikipedia Español

  • Václav Chvátal — Václav (Vašek) Chvátal (n. 1946[1] en Praga) es un informático teórico checo canadiense, profesor en el Departamento de Ciencias de la Computación e Ingeniería de Software en la Universidad Concordia de Montreal, Canadá, donde posee el grado de… …   Wikipedia Español

  • Problema de la asignación — Saltar a navegación, búsqueda El problema del asignamiento es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación… …   Wikipedia Español

  • Búsqueda tabú — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”