Stephan Mertens, Institut für Physik Theoretische, Universität Magdeburg, Postfach 4120, 39016 Magdeburg, Alemania y Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, EE.UU.
Publicado 21 de julio 2014 | Física 7, 77 (2014) | DOI: 10.1103/Physics.7.77
Herramientas matemáticas de la física están permitiendo nuevas formas de estudiar un problema de optimización clásica.
Figura 1: El problema de la concordancia bipartito euclidiana se pregunta: ¿Cómo se conecta los puntos rojos con los puntos azules de tal manera que la longitud total de conexiones en minimiza?
Figura 2 El problema del transporte Monge-Kantorovich pregunta: ¿Cómo se mueven las mejores pilas de arena para llenar los agujeros del mismo volumen total?
Optimización combinatoria problemas-de los cuales el más famoso es el problema-ha viajante pertenecido tradicionalmente a los reinos de la informática y las matemáticas, pero en las últimas décadas, importantes contribuciones también provienen de la física estadística. Los físicos han desarrollado un conjunto de potentes herramientas matemáticas para analizar los modelos de sistemas con el desorden y la frustración, y resulta que estos métodos con éxito pueden ser aplicados a problemas de optimización también [1]. En Physical Review E, Sergio Caracciolo en la Universidad de Milán, Italia, y sus colegas utilizaron un nuevo método inspirado en la resolución de problemas en física para investigar un problema clásico de optimización combinatoria, llamado el problema de la concordancia bipartito euclidiana. Se las arreglaron para calcular la función de escala del problema de optimización; a saber, cómo el costo de la solución óptima se escala con el tamaño y la dimensión del sistema [2]. Esta función es una serie infinita y si bien los enfoques anteriores han sido capaces de averiguar los primeros términos (líderes) de la serie, Carraciolo et al. son los primeros en ser capaz de calcular los próximos (subleading) los términos de la serie. Su enfoque novela explora la conexión entre el problema de la concordancia discreto y un problema de optimización continua desde el siglo 18.
El problema de la concordancia bipartito euclidiana se ilustra mejor con un ejemplo. Usted es un gerente de ventas de una empresa, y tiene n vendedores en el camino para cumplir con los clientes. Sus vendedores se encuentran actualmente en n ciudades, y quiere reubicarlos en n las nuevas ciudades de tal manera que la distancia total recorrida por su fuerza de ventas se reduce al mínimo. Usted dibuja todas las ciudades 2n en un mapa y colorear las ubicaciones actuales de los vendedores de color rojo y los nuevos destinos azules. Su tarea es entonces para que coincida con las ciudades en pares rojo-azul de tal manera que la suma de las distancias rojo-azul en su juego se minimiza (Fig. 1). El término bipartito en este problema de la concordancia se refiere al hecho de que estamos igualando elementos de dos conjuntos disyuntivas (ciudades "azul", "rojo", y). En el problema general coincidente bipartito que estamos buscando una permutación π que minimiza la función de coste E (π) = n-1Σni = 1wi, π (i), donde wij corresponden al costo de hacer coincidir tinto elemento i con el elemento azul j . En el problema de la concordancia de Euclides, wij es la distancia geométrica entre la ciudad de rojo y azul de la ciudad i j.
Como los algoritmos de ir, el problema general coincidente bipartito es "fácil" ya que sabemos algoritmos eficientes que pueden encontrar soluciones en tiempo polinómico. Pero algoritmos miran el caso problema al caso, no nos dicen mucho acerca de las propiedades genéricas de emparejamientos óptimos. Un ejemplo sencillo es la relación entre el tamaño n del problema y el valor de coste de la adaptación óptima. Para valores grandes de n esta relación de escala se vuelve independiente de casos particulares y representa una característica genérica de la problema de la concordancia. En el caso del problema de la concordancia de Euclides, esperamos que, dado un punto rojo, los puntos azules más cercanas se encuentran en un volumen del orden de O (n-1) a su alrededor. De ahí que sus distancias desde el punto rojo son de orden O (n-1 / d), donde d es la dimensión espacial. Suponiendo que en una correspondencia óptima, cada punto de color rojo se corresponde con uno de sus vecinos más cercanos, el coste óptimo debe escalar como O (n-1 / D). Este es de hecho el (primer orden) término dominante de la función de escala para valores grandes de n, por lo menos para d> 2 [3]. Carraciolo et al. ir más allá de este resultado calculando el término subleading de la función de escalado.
Las herramientas matemáticas establecidas de la física estadística funcionan mejor si el wij costos se puede considerar variables aleatorias independientes. Pero en el problema de correspondencia euclidiana aleatoria considerado por Carraciolo et al., Las posiciones aleatorias de los puntos en el espacio d-dimensional son independientes y las distancias wij resultante se correlacionan variables aleatorias. Por lo tanto Carraciolo et al. tuvieron que buscar una solución alternativa y encontraron una que es a la vez simple y sorprendente [2]: se deshacen de la naturaleza discreta del problema a juego y el recurso a una generalización continua para los que una expresión analítica para el coste mínimo puede ser calculado.
Una vez más, un ejemplo ayudará a entender este problema continua. Imaginemos que en lugar de enviar los vendedores de rojo a azul ciudades queremos mover montones de arena para rellenar agujeros (Fig. 2). El volumen total de la arena es igual al volumen total de agujeros, pero la cantidad de arena varía de pila a pila, y el volumen de los agujeros varía, también. La tarea es minimizar la distancia total que es recorrida por todos los granos de arena. Este problema se conoce como el problema del transporte Monge-Kantoróvich. Fue introducido por Gaspard Monge en 1781 [4], como el problema de "excavación y terraplenes" (les déblais et les remblais).
Ambas pilas de arena y agujeros ya no se caracterizan por puntos en el espacio, pero por distribuciones continuas. Y la arena de una pila puede ir a diferentes hoyos. El problema Monge-Kantoróvich es una generalización continua del problema de la concordancia bipartito euclidiana, y, como tal, que parece ser más difícil de analizar que la versión discreta. Pero, sorprendentemente, este no es el caso.
La solución del problema Monge-Kantorovich es trivial en el caso límite en el que sólo hay un agujero que se extiende por toda la zona, con una profundidad constante, y la arena que se distribuye de manera uniforme sobre el agujero: simplemente dejamos cada grano de arena caiga donde está. Caracciolo et al. partir de esta sencilla solución y considerar el caso de las pequeñas desviaciones de la distribución uniforme tanto para la arena y agujeros. La naturaleza continua del problema que les permite obtener una expresión analítica para el costo de transporte se espera en términos de las pequeñas desviaciones de la distribución uniforme. (El enfoque es similar a la utilizada para analizar pequeñas distorsiones transversales de una membrana elástica continua.) Las matemáticas involucradas es básicamente análisis de vectores, la ecuación de Poisson, y de Fourier de transformación-muy motivos familiares para los físicos.
Luego, los autores afirman que en el límite n grande, la discreta problema de correspondencia euclidiana es similar al caso de las pequeñas desviaciones de la distribución uniforme en el problema Monge-Kantorovich. Esta es una suposición razonable, ya que las ciudades en el problema azar juego euclidiana son muestras finitas de la distribución uniforme. Los autores no especifican la similitud en términos técnicos o incluso lo demuestran. Más bien, ellos audazmente aplican la fórmula de la solución continua para el caso discreto para obtener la escala asintótica del problema bipartito euclidiana azar coincidente en d espacio tridimensional. Su enfoque reproduce el orden de liderazgo conocido de la función de escala en todas las dimensiones d y también produce el término subleading completa para d> 2 y las constantes previamente desconocidas en el término principal para que d = 1 yd = 2.
El cambio de discreta para las variables continuas es un patrón común en la informática para diseñar potentes algoritmos para problemas de optimización [5]. Caracciolo et al. demuestran que esta idea también se puede utilizar para analizar los casos al azar de problemas de optimización combinatoria. Sus resultados mejoran nuestro conocimiento acerca de la escala del problema de la concordancia euclidiana. Queda por ver si su método puede ser extendido a otros problemas de optimización.
Physics
