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 redes con costos lineales y convexos/no lineales. Un algoritmo de subasta se ha utilizado en un entorno empresarial para determinar los mejores precios en un conjunto de productos ofrecidos a múltiples 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 otorgan 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 correspondencia 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 el ε-escalamiento [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 de preflujo-empuje para el 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 de 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 en 1991 una variación posterior del algoritmo de subasta que resuelve problemas de ruta más corta . [5] Es un algoritmo simple para encontrar rutas más cortas en un grafo dirigido . En el caso de un solo origen/un solo destino, el algoritmo de subasta mantiene una sola ruta que comienza en el origen, que luego se extiende o contrae por un solo nodo en cada iteración. Simultáneamente, como máximo se ajustará 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 que el número total de nodos); Consulte el artículo de Bertsekas, Pallottino y Scutella, Algoritmos de subasta polinomial para caminos más cortos.
De Leone y Pretolani definieron algoritmos de subasta para problemas de hipertrayecto más corto en 1998. Este también es un algoritmo de subasta paralela para correspondencia bipartita ponderada, descrito por E. Jason Riedy en 2004. [6]
Los algoritmos de subasta (secuencial) para el problema de la ruta más corta han sido objeto de experimentos que se han publicado 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.
Se cree que el algoritmo de subasta de Bertsekas para encontrar caminos más cortos dentro de un gráfico dirigido funciona muy bien en gráficos aleatorios y en problemas con pocos destinos. [5]