Optimización combinatoria

Subcampo de 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ínima ("MST") y el problema de la mochila . En muchos de estos problemas, como los mencionados anteriormente, la búsqueda exhaustiva no es manejable, por lo que en su lugar se debe recurrir a algoritmos especializados que descartan rápidamente grandes partes del espacio de búsqueda o 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 importantes aplicaciones en varios campos, incluyendo inteligencia artificial , aprendizaje automático , teoría de subastas , ingeniería de software , VLSI , matemáticas aplicadas e informática teórica .

Alguna literatura de investigación ^[2] considera que la optimización discreta consiste en programación entera junto con optimización combinatoria (que a su vez se compone de problemas de optimización que tratan con estructuras gráficas ), aunque todos estos temas tienen literatura de investigación estrechamente entrelazada. ^{[ se necesita aclaración ]}

Aplicaciones

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

• Logística ^[3]
• Optimización de la cadena de suministro ^[4]
• Desarrollando la mejor red aérea de radios y destinos
• Decidir qué taxis de una flota dirigirse para recoger las tarifas
• 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 las ciencias de la Tierra (por ejemplo, caudales de embalses ) ^[5]

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 cubiertos por este marco son los caminos más cortos y los árboles de camino más corto , los flujos y circulaciones , los árboles de expansión , las coincidencias y los problemas matroides .

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

• Casos especiales del problema en cuestión que se pueden resolver exactamente en tiempo polinómico (p. ej., problemas manejables 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 polinómico 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 peor comportamiento de los problemas NP-completos (por ejemplo, instancias de TSP del mundo real con decenas de miles de nodos ^[6] ).

Los problemas de optimización combinatoria pueden verse como la búsqueda del mejor elemento de algún conjunto de elementos discretos; por lo tanto, en principio, se puede utilizar cualquier tipo de algoritmo de búsqueda o metaheurística para resolverlos. Quizás los enfoques ^{[ palabras de comadreja ]} más universalmente aplicables son la ramificación y el límite (un algoritmo exacto que puede detenerse en cualquier momento para que sirva como heurístico), la ramificación y el corte (utiliza optimización lineal para generar límites), los dinámicos . programación (una construcción de solución recursiva con ventana de búsqueda limitada) y búsqueda tabú (un algoritmo de intercambio de tipo codicioso). 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 polinómico). Dado que algunos problemas de optimización discretos son NP-completos , como el problema del viajante (decisión), ^[7] esto se espera 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 en particular . Por ejemplo, si hay un gráfico que contiene vértices y , un problema de optimización podría ser "encontrar una ruta desde hasta que utilice la menor cantidad de aristas". Este problema podría tener una respuesta de, digamos, 4. Un problema de decisión correspondiente sería "¿hay una ruta desde hasta que utilice 10 aristas o menos?" Este problema puede responderse 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 caracteriza más naturalmente como un problema de optimización. ^[8]

Problema de optimización NP

Un problema de optimización NP (NPO) es un problema de optimización combinatoria con las siguientes condiciones adicionales. ^[9] Tenga en cuenta que los polinomios mencionados 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 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 polinómico , y ${\displaystyle \{\,x\,\mid \,x\in I\,\}}$ ${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$
• ${\displaystyle m}$es computable en tiempo polinómico .

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 también se denomina 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 cuales las versiones de decisión son NP-completas . Tenga en cuenta que las relaciones de dureza son siempre con respecto a alguna reducción. Debido a la conexión entre los algoritmos de aproximación y los problemas de optimización computacional, en este tema se prefieren las reducciones que preservan la aproximación en algún aspecto a las habituales reducciones 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 completos. ^[10]

NPO se divide en las siguientes subclases según su proximidad: ^[9]

• NPO(I) : Igual a FPTAS . Contiene el problema de la mochila .
• NPO(II) : Es igual a PTAS . Contiene el problema de programación de 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 del costo óptimo (para problemas de maximización). En el libro de Hromkovič ^{[ ¿cuál? ]} , excluidos de esta clase están 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 polinomial que se aproximan a la solución óptima mediante una relació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 portada del conjunto .
• NPO(V) : :La clase de problemas NPO con algoritmos de tiempo polinomial que se aproximan a 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 TSP y el problema de la camarilla .

Un problema NPO se llama polinomialmente acotado (PB) si, para cada instancia y para cada solución , la medida está acotada por una función polinómica 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 para vendedores ambulantes por las 15 ciudades más grandes de Alemania . Es el más corto entre los 43.589.145.600 ^[11] recorridos posibles que visitan cada ciudad exactamente una vez.

• problema de asignacion
• 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 entera
• programación del taller de trabajo
• problema de mochila
• Variables mínimas relevantes en sistema lineal.
• Árbol de expansión mínimo
• Problema de programación de enfermeras
• Establecer problema de portada
• Programación de talentos
• Problema del vendedor ambulante
• Problema de reprogramación de vehículos
• Problema de ruta de vehículos
• Problema de asignación de objetivos de armas

Ver también

• Gráfico compuesto de restricciones

Notas

1. Schrijver 2003, pag. 1.
2. Optimización discreta. Elsevier. Archivado desde el original el 5 de julio de 2013 . Consultado el 8 de junio de 2009 .
3. Sbihi, Abdelkader; Iglesia, Richard W. (2007). «Optimización combinatoria y Logística Verde» (PDF) . 4O . 5 (2): 99-116. doi :10.1007/s10288-007-0047-3. S2CID  207070217. Archivado (PDF) desde el original el 26 de diciembre de 2019 . Consultado el 26 de diciembre de 2019 .
4. Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Peton, Olivier (2015). "Diseño de red de cadena de suministro sostenible: una revisión orientada a la optimización" (PDF) . Omega . 54 : 11–32. doi :10.1016/j.omega.2015.01.006. Archivado (PDF) desde el original el 26 de diciembre de 2019 . Consultado el 26 de diciembre de 2019 .
5. Hobé, Alex; Vogler, Daniel; Seybold, Martín P.; Ebigbo, Anozie; Settgast, Randolph R.; Sarre, Martín 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 Bib : 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 .
6. Cocinero 2016.
7. "Aproximación-TSP" (PDF) . Archivado (PDF) desde el original el 1 de marzo de 2022 . Consultado el 17 de febrero de 2022 .
8. Ausiello, Giorgio; et al. (2003), Complejidad y aproximación (edición corregida), Springer, ISBN 978-3-540-65431-5
9. Hromkovic, Juraj (2002), Algorítmica para problemas difíciles , Textos de informática teórica (2ª ed.), Springer, ISBN 978-3-540-44134-2
10. Kann, Viggo (1992), Sobre la aproximabilidad de los problemas de optimización NP-completos , Real Instituto de Tecnología, Suecia, ISBN 91-7170-082-X
11. Tome una ciudad y tome todos los pedidos posibles de las otras 14 ciudades. Luego divide por dos porque no importa en qué dirección en el tiempo se suceden: 14!/2 = 43.589.145.600.

Referencias

• Beasley, JE "Programación entera" (notas de la conferencia).

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

• Cocinero, William (2016). "Tours TSP óptimos". Universidad de Waterloo . (Información sobre los casos de TSP más grandes resueltos 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 conferencias de física. vol. 679. Saltador. Código Bib : 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". Mod. Rev. Física . 80 (3): 1061. arXiv : 0801.2193 . Código Bib : 2008RvMP...80.1061D. CiteSeerX  10.1.1.563.9990 . doi : 10.1103/RevModPhys.80.1061. S2CID  14255125.

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

• Lee, Jon (2004). Un primer curso en optimización combinatoria. Prensa de la Universidad de Cambridge. 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, Alejandro (2003). Optimización combinatoria: poliedros y eficiencia. Algoritmos y Combinatoria. vol. 24. Saltador. ISBN 9783540443896.

• Schrijver, Alejandro (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 de optimización combinatoria (PDF) .

• Sierksma, Gerard; Ghosh, Diptesh (2010). Redes en Acción; Ejercicios de texto e ordenador en optimización de redes . Saltador. 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 informática bioinspirada para problemas de optimización combinatoria. Biblioteca de referencia de sistemas inteligentes. Saltador. ISBN 978-3-642-40178-7.

enlaces externos

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