El término " algoritmo de subasta " [1] se aplica a varias variaciones de un algoritmo de optimización combinatoria que resuelve problemas de asignación y problemas de optimización de red con costo lineal y convexo / no lineal. Se ha utilizado un algoritmo de subasta en un entorno empresarial para determinar los mejores precios en un conjunto de productos ofrecidos a varios compradores. Es un procedimiento iterativo, por lo que el nombre "algoritmo de subasta" está relacionado con una subasta de ventas , donde se comparan múltiples ofertas para determinar la mejor oferta, y las ventas finales se dirigen a los postores más altos.
La forma original del algoritmo de subasta es un método iterativo para encontrar los precios óptimos y una asignación que maximiza el beneficio neto en un gráfico bipartito , el problema de igualación de peso máximo (MWM). [2] [3] Este algoritmo fue propuesto por primera vez por Dimitri Bertsekas en 1979.
Las ideas del algoritmo de subasta y la escala ε [1] también son fundamentales en los algoritmos de preflujo-empuje para problemas de flujo de red lineal de un solo producto. De hecho, el algoritmo preflujo-empuje para flujo máximo se puede derivar aplicando el algoritmo de subasta original de 1979 al problema de flujo máximo después de reformularlo como un problema de asignación. Además, el algoritmo preflujo-empuje para el problema de flujo de costo mínimo lineal es matemáticamente equivalente al método de relajación ε, que se obtiene aplicando el algoritmo de subasta original después de reformular el problema como un problema de asignación equivalente. [4]
Bertsekas introdujo una variación posterior del algoritmo de subasta que resuelve problemas de ruta más corta en 1991. [5] Es un algoritmo simple para encontrar las rutas más cortas en un gráfico dirigido . En el caso de origen único / destino único, el algoritmo de subasta mantiene una ruta única que comienza en el origen, que luego es ampliada o contraída por un solo nodo en cada iteración. Simultáneamente, se ajustará como máximo una variable dual en cada iteración, para mejorar o mantener el valor de una función dual. En el caso de múltiples orígenes, el algoritmo de subasta es adecuado para el cálculo paralelo. [5] El algoritmo está estrechamente relacionado con los algoritmos de subasta para otros problemas de flujo de red. [5] Según experimentos computacionales, el algoritmo de subasta es generalmente inferior a otros algoritmos de última generación para el problema de la ruta más corta de todos los destinos, pero es muy rápido para problemas con pocos destinos (sustancialmente más de uno y sustancialmente menos de el número total de nodos); ver el artículo de Bertsekas, Pallottino y Scutella, Polynomial Auction Algorithms for Shortest Paths .
De Leone y Pretolani definieron algoritmos de subasta para problemas de hiperruta más cortos en 1998. Este es también un algoritmo de subasta paralela para la correspondencia bipartita ponderada, descrito por E. Jason Riedy en 2004. [6]
Comparaciones
Los algoritmos de subasta (secuenciales) para el problema de la ruta más corta han sido objeto de experimentos que se han informado en artículos técnicos. [7] Los experimentos muestran claramente que el algoritmo de subasta es inferior a los algoritmos de ruta más corta de última generación para encontrar la solución óptima de problemas de origen único a todos los destinos. [7]
Aunque con el algoritmo de subasta el beneficio total aumenta monótonamente con cada iteración, en el algoritmo húngaro (de Kuhn, 1955; Munkres, 1957) el beneficio total aumenta estrictamente con cada iteración.
El algoritmo de subasta de Bertsekas para encontrar las rutas más cortas dentro de un gráfico dirigido tiene fama de funcionar muy bien en gráficos aleatorios y en problemas con pocos destinos. [5]
Ver también
Referencias
- ↑ a b Dimitri P. Bertsekas . "Un algoritmo distribuido para el problema de asignación", artículo original, 1979 .
- ^ MG Resende, PM Pardalos. "Manual de optimización en telecomunicaciones", 2006
- ^ M. Bayati, D. Shah, M. Sharma. "Un algoritmo de igualación de peso máximo de producto máximo más simple y el algoritmo de subasta", 2006, página web PDF: MIT-bpmwm-PDF Archivado 2017-09-21 en Wayback Machine .
- ^ Dimitri P. Bertsekas. "Algoritmos de relajación distribuida para problemas de flujo de red lineal", Proc. of 25th IEEE CDC, Athens, Greece, 1986, pp. 2101-2106, en línea de IEEEXplore [1]
- ↑ a b c d Dimitri P. Bertsekas. "Un algoritmo de subasta para rutas más cortas", SIAM Journal on Optimization , 1: 425—447, 1991, PSU-bertsekas91auction
- ^ "El algoritmo de subasta paralela para el emparejamiento bipartito ponderado", E. Jason Riedy, UC Berkeley, febrero de 2004, [2] .
- ^ a b Larsen, Jesper; Pedersen, Ib (1999). "Experimentos con el algoritmo de subasta para el problema de la ruta más corta" . Revista Nórdica de Computación . 6 (4): 403–42. ISSN 1236-6064 ., ver también Una nota sobre el rendimiento práctico del algoritmo de subasta para el camino más corto Archivado 2011-06-05 en Wayback Machine (1997) por el primer autor.
enlaces externos
- Dimitri P. Bertsekas. "Optimización de red lineal", MIT Press, 1991, en línea .
- Dimitri P. Bertsekas. "Optimización de la red: modelos continuos y discretos", Athena Scientific, 1998 .
- Dimitri P. Bertsekas. "Un algoritmo de subasta para rutas más cortas", SIAM Journal on Optimization , 1: 425—447, 1991, página web: PSU-bertsekas91auction .
- DP Bertsekas, S. Pallottino, MG Scutella. "Algoritmos de subasta de polinomios para rutas más cortas" , Optimización computacional y aplicaciones, vol. 4, 1995, págs. 99-125 .
- Implementación del algoritmo de subasta de Bertsekas en Matlab por Florian Bernard, página web: Matlab File Exchange .