Optimización combinatoria

Subcampo de la optimización matemática

Un árbol de expansión mínimo de un gráfico plano ponderado . Encontrar un árbol de expansión mínimo es un problema común que involucra 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ínimo ("MST") y el problema de la mochila . En muchos de estos problemas, como los mencionados anteriormente, la búsqueda exhaustiva no es factible, por lo que se debe recurrir en su lugar 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 de operaciones , la teoría de algoritmos y la teoría de la complejidad computacional . Tiene aplicaciones importantes en varios campos, incluidos 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 .

Aplicaciones

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

• Logística ^[2]
• Optimización de la cadena de suministro ^[3]
• Desarrollar la mejor red de radios y destinos de aerolíneas
• Decidir qué taxis de una flota utilizar 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]

Métodos

Existe una gran cantidad de literatura sobre algoritmos de tiempo polinomial para ciertas clases especiales de optimización discreta. Una cantidad considerable de ella está unificada por la teoría de la programación lineal . Algunos ejemplos de problemas de optimización combinatoria que se cubren en 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 , el 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 manejables con parámetros fijos )
• algoritmos que funcionan bien en instancias "aleatorias" (por ejemplo, para el problema del viajante de comercio )
• 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 no necesariamente exhiben el peor comportamiento en problemas NP-completos (por ejemplo, instancias TSP del mundo real con decenas de miles de nodos ^[5] ).

Los problemas de optimización combinatoria pueden considerarse como la búsqueda del mejor elemento de un conjunto de elementos discretos; por lo tanto, en principio, se puede utilizar cualquier tipo de algoritmo de búsqueda o metaheurística para resolverlos. Los enfoques ampliamente aplicables incluyen ramificación y acotación (un algoritmo exacto que se puede detener en cualquier momento para que sirva como heurística), ramificación y corte (utiliza la optimización lineal para generar acotamientos), programación dinámica (una construcción de solución recursiva con una 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 se garantiza que se ejecuten rápidamente (en tiempo polinomial). Dado que algunos problemas de optimización discretos son NP-completos , como el problema del viajante (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 . Por ejemplo, si hay un gráfico que contiene vértices y , un problema de optimización podría ser "encontrar un camino desde a que use 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 a que use 10 o menos aristas?" Este problema se puede responder con un simple 'sí' o 'no'. ${\displaystyle m_{0}}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

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

Problema de optimización NP

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

• el tamaño de cada solución factible está acotado polinomialmente en el tamaño de la instancia dada , ${\displaystyle y\in f(x)}$ ${\displaystyle x}$
• los idiomas y pueden ser reconocidos en tiempo polinomial , y ${\displaystyle \{\,x\,\mid \,x\in I\,\}}$ ${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$
• ${\displaystyle m}$es computable en tiempo polinomial .

Esto implica que el problema de decisión correspondiente está en NP . En informática, los problemas de optimización interesantes suelen tener las propiedades anteriores y, por tanto, son problemas NPO. Un problema se denomina además problema de optimización P (PO) si existe un algoritmo que encuentra soluciones óptimas en tiempo polinomial. A menudo, cuando se trata de la clase NPO, uno está interesado en problemas de optimización para los que las versiones de decisión son NP-completas . Tenga en cuenta que las relaciones de dureza siempre son con respecto a alguna reducción. Debido a la conexión entre los algoritmos de aproximación y los problemas de optimización computacional, las reducciones que preservan la aproximación en algún aspecto son preferidas para este tema que las reducciones habituales de Turing y Karp . Un ejemplo de tal reducción sería la reducción L. Por esta razón, los problemas de optimización con versiones de decisión NP-completas no necesariamente se denominan NPO-completas. ^[9]

La NPO se divide 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 igual al costo óptimo (para problemas de maximización). En el libro de Hromkovič ^{[ ¿cuál? ]} , se excluyen de esta clase todos los problemas NPO(II) excepto si P=NP. Sin la exclusión, es igual a APX. Contiene MAX-SAT y TSP métrico . ${\displaystyle 1/c}$
• NPO(IV) : La clase de problemas NPO con algoritmos de tiempo polinómico que aproximan la solución óptima mediante una razón que es polinómica en un logaritmo del tamaño de la entrada. En el libro de Hromkovič, todos los problemas NPO(III) están excluidos de esta clase a menos que P=NP. Contiene 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 relación limitada por alguna función en n. En el libro de Hromkovic, todos los problemas NPO(IV) están excluidos de esta clase a menos que P=NP. Contiene el problema TSP y el problema de camarilla .

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

Problemas específicos

Un recorrido óptimo de un vendedor ambulante por las 15 ciudades más grandes de Alemania . Es el más corto de los 43.589.145.600 ^[10] recorridos posibles que visitan cada ciudad exactamente una vez.

• Problema de asignación
• Problema de embalaje del contenedor
• Problema de cierre
• Problema de satisfacción de restricciones
• Problema de corte de stock
• Problema del conjunto dominante
• Programación de números enteros
• Programación de talleres de trabajo
• Problema de la mochila
• Variables mínimas relevantes en un sistema lineal
• Árbol de expansión mínimo
• Problema de programación de enfermeras
• Problema con la cubierta del conjunto
• Programación de talentos
• Problema del viajante de comercio
• Problema de reprogramación de vehículos
• Problema de ruta del vehículo
• Problema de asignación de objetivos de armas

Véase también

• Gráfico compuesto con restricciones

Notas

1. Schrijver 2003, pág. 1.
2. Sbihi, Abdelkader; Eglese, Richard W. (2007). "Optimización combinatoria y logística verde" (PDF) . 4OR . 5 (2): 99–116. doi :10.1007/s10288-007-0047-3. S2CID  207070217. Archivado (PDF) desde el original el 2019-12-26 . Consultado el 2019-12-26 .
3. Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). "Sustainable supply chain network design: An optimized-oriented review" (PDF) . Omega . 54 : 11–32. doi :10.1016/j.omega.2015.01.006. Archivado (PDF) desde el original el 2019-12-26 . Consultado el 2019-12-26 .
4. Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O. (2018). "Estimación de caudales de fluidos a través de redes de fracturas mediante optimización combinatoria". Avances en recursos hídricos . 122 : 85–97. arXiv : 1801.08321 . Código Bibliográfico :2018AdWR..122...85H. doi :10.1016/j.advwatres.2018.10.002. S2CID  119476042. Archivado desde el original el 21 de agosto de 2020 . Consultado el 16 de septiembre de 2020 .
5. Cocinar 2016.
6. "Aproximación-TSP" (PDF) . Archivado (PDF) del original el 2022-03-01 . Consultado el 2022-02-17 .
7. Ausiello, Giorgio; et al. (2003), Complejidad y aproximación (edición corregida), Springer, ISBN 978-3-540-65431-5
8. Hromkovic, Juraj (2002), Algoritmia para problemas difíciles , Textos en informática teórica (2.ª ed.), Springer, ISBN 978-3-540-44134-2
9. Kann, Viggo (1992), Sobre la aproximabilidad de problemas de optimización NP-completos , Instituto Real de Tecnología, Suecia, ISBN 91-7170-082-X
10. Tomemos una ciudad y tomemos todos los órdenes posibles de las otras 14 ciudades. Luego dividamos por dos, porque no importa en qué dirección en el tiempo aparezcan una después de la otra: 14!/2 = 43.589.145.600.

Referencias

• Beasley, JE "Programación entera" (notas 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). “Viajes óptimos de TSP”. Universidad de Waterloo . (Información sobre las instancias de TSP más grandes 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 continuamente actualizado 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 . Apuntes de clase en física. 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. 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. págs. 1–68.

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

• Sierksma, Gerard; Ghosh, Diptesh (2010). Redes en acción: ejercicios de texto y computadora 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 . CRC Press. 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.

Enlaces externos

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