Optimización combinatoria

La optimización combinatoria es un subcampo de la optimización matemática que consiste en encontrar un objeto óptimo a partir de un conjunto finito de objetos, ^{[ 1 ]} donde el conjunto de soluciones factibles es discreto o puede reducirse a un conjunto discreto. Los problemas típicos de optimización combinatoria son el problema del viajante ("TSP"), el problema del árbol de expansión mínima ("MST") y el problema de la mochila . En muchos de estos problemas, como los mencionados anteriormente, la búsqueda exhaustiva no es viable, por lo que se debe recurrir a algoritmos especializados que descartan rápidamente grandes partes del espacio de búsqueda o a algoritmos de aproximación .

La optimización combinatoria está relacionada con la investigación operativa , la teoría de algoritmos y la teoría de la complejidad computacional . Tiene importantes aplicaciones en diversos campos, como la inteligencia artificial , el aprendizaje automático , la teoría de subastas , la ingeniería de software , VLSI , las matemáticas aplicadas y la informática teórica .

Las aplicaciones básicas de la optimización combinatoria incluyen, entre otras:

• Logística ^{[ 2 ]}
• Optimización de la cadena de suministro ^{[ 3 ]}
• Desarrollar la mejor red de aerolíneas con rutas y destinos.
• Decidir qué taxis de una flota asignar para recoger pasajeros.
• Determinar la forma óptima de entregar paquetes
• Asignar puestos de trabajo a las personas de forma óptima
• Diseño de redes de distribución de agua
• problemas de ciencias de la Tierra (por ejemplo, caudales de embalses ) ^{[ 4 ]}

Existe una amplia bibliografía sobre algoritmos de tiempo polinomial para ciertas clases especiales de optimización discreta. Gran parte de ella se unifica mediante la teoría de la programación lineal . Algunos ejemplos de problemas de optimización combinatoria que abarca este marco son los caminos más cortos y los árboles de caminos más cortos , los flujos y las circulaciones , los árboles de expansión , los problemas de emparejamiento y los problemas de matroides .

Para problemas de optimización discreta NP-completos , la literatura de investigación actual incluye los siguientes temas:

• Casos especiales del problema en cuestión que se pueden resolver exactamente en tiempo polinomial (por ejemplo, problemas tratables con parámetros fijos ).
• algoritmos que funcionan bien en instancias "aleatorias" (por ejemplo, para el problema del viajante ).
• algoritmos de aproximación que se ejecutan en tiempo polinomial y encuentran una solución cercana a la óptima
• Algoritmos de aproximación parametrizados que se ejecutan en tiempo FPT y encuentran una solución cercana al óptimo.
• resolver instancias del mundo real que surgen en la práctica y que no necesariamente exhiben el comportamiento del peor caso de los problemas NP-completos (por ejemplo, instancias del TSP del mundo real con decenas de miles de nodos ^{[ 5 ]} ).

Los problemas de optimización combinatoria pueden verse como la búsqueda del mejor elemento de un conjunto de elementos discretos; por lo tanto, en principio, cualquier tipo de algoritmo de búsqueda o metaheurística puede utilizarse para resolverlos. Los enfoques ampliamente aplicables incluyen ramificación y acotación (un algoritmo exacto que puede detenerse en cualquier momento para servir como heurística), ramificación y corte (utiliza optimización lineal para generar límites), programación dinámica (una construcción de solución recursiva con ventana de búsqueda limitada) y búsqueda tabú (un algoritmo de intercambio de tipo voraz). Sin embargo, no se garantiza que los algoritmos de búsqueda genéricos encuentren primero una solución óptima, ni que se ejecuten rápidamente (en tiempo polinomial). Dado que algunos problemas de optimización discreta son NP-completos , como el problema del viajante (de decisión), ^{[ 6 ]} esto es de esperar a menos que P=NP .

Para cada problema de optimización combinatoria, existe un problema de decisión correspondiente que pregunta si existe una solución factible para alguna medida particular.${\displaystyle m_{0}}$Por ejemplo, si hay un gráfico${\displaystyle G}$que contiene vértices${\displaystyle u}$y${\displaystyle v}$, un problema de optimización podría ser "encontrar un camino desde${\displaystyle u}$a${\displaystyle v}$que utiliza la menor cantidad de aristas". Este problema podría tener una respuesta de, digamos, 4. Un problema de decisión correspondiente sería "¿hay un camino desde${\displaystyle u}$a${\displaystyle v}$¿Que utiliza 10 o menos aristas? Este problema se puede responder con un simple "sí" o "no".

El campo de los algoritmos de aproximación se ocupa de algoritmos para encontrar soluciones casi óptimas a problemas difíciles. La versión habitual de decisión resulta, por lo tanto, una definición inadecuada del problema, ya que solo especifica soluciones aceptables. Si bien podríamos introducir problemas de decisión adecuados, el problema se caracteriza entonces de forma más natural como un problema de optimización. ^{[ 7 ]}

Un problema de optimización NP (NPO) es un problema de optimización combinatoria con las siguientes condiciones adicionales. ^{[ 8 ]} Nótese que los polinomios a los que se hace referencia a continuación son funciones del tamaño de las entradas de las funciones respectivas, no del tamaño de algún conjunto implícito de instancias de entrada.

• el tamaño de cada solución factible${\displaystyle y\in f(x)}$, dónde${\displaystyle f(x)}$denota el conjunto de soluciones factibles para la instancia${\displaystyle x}$, está acotado polinómicamente en el tamaño de la instancia dada${\displaystyle x}$,
• los idiomas de instancias válidas${\displaystyle \{\,x\,\mid \,x\in I\,\}}$y de pares válidos instancia-solución${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$puede ser reconocido en tiempo polinomial y
• La medida${\displaystyle m(x,y)}$de una solución${\displaystyle y}$problema${\displaystyle x}$es computable en tiempo polinomial .

Esto implica que el problema de decisión correspondiente pertenece a NP . En informática, los problemas de optimización interesantes suelen tener las propiedades anteriores y, por lo tanto, son problemas NPO. Un problema se denomina además problema de P-optimización (PO) si existe un algoritmo que encuentra soluciones óptimas en tiempo polinomial. A menudo, al tratar con la clase NPO, interesan los problemas de optimización cuyas versiones de decisión son NP-completas . Cabe señalar que las relaciones de dificultad siempre se refieren a alguna reducción. Debido a la conexión entre los algoritmos de aproximación y los problemas de optimización computacional, en este ámbito se prefieren las reducciones que preservan la aproximación en algún aspecto a las reducciones habituales de Turing y Karp . Un ejemplo de tal reducción sería la L-reducción . Por esta razón, los problemas de optimización con versiones de decisión NP-completas no se denominan necesariamente NPO-completos. ^{[ 9 ]}

Las organizaciones sin fines de lucro se dividen en las siguientes subclases según su aproximabilidad: ^{[ 8 ]}

• NPO(I) : Es igual a FPTAS . Contiene el problema de la mochila .
• NPO(II) : Es igual a PTAS . Contiene el problema de programación Makespan .
• NPO(III) : La clase de problemas NPO que tienen algoritmos de tiempo polinomial que calculan soluciones con un costo como máximo c veces el costo óptimo (para problemas de minimización) o un costo al menos${\displaystyle 1/c}$del costo óptimo (para problemas de maximización). En el libro de Hromkovič Algorithms for Hard Problems , se excluyen de esta clase todos los problemas NPO(II) salvo que P=NP. ^{[ 8 ]} Sin la exclusión, es igual a APX. Contiene MAX-SAT y TSP métrico .
• NPO(IV) : Clase de problemas NPO con algoritmos de tiempo polinomial que aproximan la solución óptima mediante una razón polinomial en el logaritmo del tamaño de la entrada. En el libro de Hromkovič, todos los problemas NPO(III) se excluyen de esta clase a menos que P=NP. Incluye el problema de cobertura de conjuntos .
• NPO(V) : La clase de problemas NPO con algoritmos de tiempo polinomial que aproximan la solución óptima mediante una razón acotada por alguna función en n. En el libro de Hromkovic, todos los problemas NPO(IV) se excluyen de esta clase a menos que P=NP. Contiene el problema del viajante y el problema de la camarilla .

Un problema NPO se denomina acotado polinomialmente (PB) si, para cada instancia${\displaystyle x}$y para cada solución${\displaystyle y\in f(x)}$la medida${\displaystyle m(x,y)}$está acotado por una función polinómica del tamaño de${\displaystyle x}$La clase NPOPB es la clase de problemas NPO que están acotados polinomialmente.

• Problema de asignación
• Problema de empaquetamiento de contenedores
• El problema del cartero chino
• Problema de cierre
• Problema de satisfacción de restricciones
• Problema con el material de corte
• Problema del conjunto dominante
• Programación entera
• Programación de talleres de producción
• Problema de la mochila
• Problema del centro k métrico / centro k de vértice
• Variables mínimas relevantes en un sistema lineal
• árbol de expansión mínima
• Problema de programación de enfermeras
• Problema de la estrella del anillo
• Problema de la cubierta del conjunto
• Programación de talentos
• El problema del viajante
• Problema de reprogramación de vehículos
• Problema de enrutamiento de vehículos
• problema de asignación de objetivos de armas

• Grafo compuesto de restricciones : grafo no dirigido ponderado por nodos asociado a un problema de optimización combinatoria dado. 

• Beasley, JE "Programación entera" (apuntes de clase).

• Cook, William J .; Cunningham, William H.; Pulleyblank, William R .; Schrijver, Alexander (1997). Optimización combinatoria . Wiley. ISBN 0-471-55894-X.

• Cook, William (2016). "Recorridos óptimos del TSP" . Universidad de Waterloo .(Información sobre las instancias más grandes del problema del viajante resueltas hasta la fecha).

• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (eds.). "Un compendio de problemas de optimización de NP" .(Este es un catálogo actualizado continuamente de resultados de aproximabilidad para problemas de optimización NP).

• Das, Arnab; Chakrabarti, Bikas K , eds. (2005). Recocido cuántico y métodos de optimización relacionados . Lecture Notes in Physics. Vol.  679. Springer. Bibcode : 2005qnro.book.....D . ISBN 978-3-540-27987-7.

• Das, Arnab; Chakrabarti, Bikas K (2008). "Coloquio: Recocido cuántico y computación cuántica analógica". Rev. Mod. Phys . 80 (3): 1061. arXiv : 0801.2193 . Bibcode : 2008RvMP...80.1061D . CiteSeerX 10.1.1.563.9990 . doi : 10.1103/RevModPhys.80.1061 . S2CID 14255125 .  

• Lawler, Eugene (2001). Optimización combinatoria: redes y matroides . Dover. ISBN 0-486-41453-1.

• Lee, Jon (2004). Un primer curso de optimización combinatoria . Cambridge University Press. ISBN 0-521-01012-8.

• Papadimitriou, Christos H.; Steiglitz, Kenneth (julio de 1998). Optimización combinatoria  : algoritmos y complejidad . Dover. ISBN 0-486-40258-4.

• Schrijver, Alexander (2003). Optimización combinatoria: poliedros y eficiencia (PDF) . Algoritmos y combinatoria. Vol.  24. Springer. ISBN 9783540443896.

• Schrijver, Alexander (2005). "Sobre la historia de la optimización combinatoria (hasta 1960)" (PDF) . En Aardal, K .; Nemhauser, GL; Weismantel, R. (eds.). Manual de optimización discreta . Elsevier. pp. 1–68 . 

• Schrijver, Alexander (1 de febrero de 2006). Un curso de optimización combinatoria (PDF) .

• Sierksma, Gerard ; Ghosh, Diptesh (2010). Redes en acción: texto y ejercicios informáticos sobre optimización de redes . Springer. ISBN 978-1-4419-5512-8.

• Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica . Prensa CRC. ISBN 978-1-498-71016-9.

• Pintea, CM. (2014). Avances en computación bioinspirada para problemas de optimización combinatoria . Biblioteca de referencia de sistemas inteligentes. Springer. ISBN 978-3-642-40178-7.

• Revista de Optimización Combinatoria
• Taller de Optimización Combinatoria de Aussois
• Plataforma de optimización combinatoria en Java (código fuente abierto)
• ¿Por qué es difícil organizar los horarios de las personas?
• Clases de complejidad para problemas de optimización / Stefan Kugele