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. Se ha utilizado un algoritmo de subasta 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 van a parar 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 centrales en los algoritmos de preflujo-empuje para problemas de flujo de redes lineales 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 que el problema se reformula como un problema de asignación equivalente. [4]
Bertsekas introdujo una variación posterior del algoritmo de subasta que resuelve problemas de caminos más cortos en 1991. [5] Es un algoritmo simple para encontrar caminos más cortos 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 se extiende o contrae mediante un único 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 orígenes múltiples, 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 del camino más corto para 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); consulte el artículo de Bertsekas, Pallottino y Scutella, Algoritmos de subasta polinomiales para caminos más cortos.
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 emparejamiento bipartito ponderado, descrito por E. Jason Riedy en 2004. [6]
Los algoritmos de subasta (secuencial) para el problema del camino más corto 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 los caminos más cortos dentro de un gráfico dirigido tiene fama de funcionar muy bien en gráficos aleatorios y en problemas con pocos destinos. [5]