Алгоритм аукціону

Термін алгори́тм аукціо́ну^[1] (англ. Auction algorithm) використовується для позначення кількох варіантів алгоритмів комбінованої оптимізації при вирішенні задач призначення і задач мережної оптимізації з лінійними чи нелінійними витратами. Алгоритм аукціону використовується у бізнес рішеннях для визначення найкращих цін на набір продуктів, запропонованих для кількох покупців. Він використовує ітераційний метод, оскільки назва «алгоритм аукціону» відсилає до поняття торгового аукціону, де паралельні ставки порівнюються для визначення найкращої пропозиції, а остаточний продаж відбувається за найвищої ставки.

Початковою формою алгоритму аукціону був метод ітерацій для пошуку оптимальної ціни і призначення, які максимізували б чисті вигоди у двочастковому графіку, у задачах парування (теорії графів)^[2]. Цей алгоритм вперше запропонував Дімітрій Берцекас у 1979 р. Докладний аналіз і розширення для більш загальних задач мережною оптимізації (іпсилон-послаблення і алгоритми мережних аукціонів) наведений у його книжках з мережної оптимізації «Оптимізація лінійних мереж» (1991) та «Мережна оптимізація: Неперервні та Дискретні моделі» (1998). Алгоритм аукціону має найвищу обчислювальну складність, згідно з цими книжками, і вважається одним з найшвидших методів вирішення простих споживацьких задач мережної оптимізації.

Пізніший варіант алгоритму аукціону, котрий розв'язує задачу про найкоротший шлях, був запропонований Берцекасом у 1991 р.^[3] Це простий алгоритм для знаходження найкоротшого шляху в орієнтованому графі^[3]. У випадку однієї початкової та однією точки призначення, алгоритм аукціону будує один шлях від початкової точки, який розширюється пізніше чи обумовлюється окремим вузлом при кожній ітерації. При цьому щонайбільше одна подвійна змінна буде відкоригована при одній ітерації для того, щоб вдосконалити або зберегти значення подвійної функції. Алгоритм аукціону добре підходить для паралельного обрахунку у випадку кількох початкових точок^[3]. Також цей алгоритм тісно пов'язаний з алгоритмами аукціону для інших задач мережних потоків^[3]. Згідно з експериментальними обчисленнями, алгоритм аукціону є нижчим порівняно до інших впроваджених алгоритмів для усіх проблем найкоротшого шляху, але є дуже швидким для проблем з невеликою кількістю точок призначень (переважно більше однієї та менше за загальну кількість вузлів), див. статтю Берцекас, Паллотіно і Скутелла, Polynomial Auction Algorithms for Shortest Paths^{[недоступне посилання з грудня 2019]}.

Алгоритми аукціону для найкоротшого гіпершляху були визначені Де Леоне та Претолані у 1998 р.^[3] це також алгоритм паралельного аукціону для зваженого двочасткового зіставлення, описаного Е. Джейсоном Ріді у 2004.^[4]

Порівняння

(Послідовний) алгоритм аукціону для задач найкоротшого шляху став предметом експериментів, описаних в спеціалізованих технічних виданнях^[5]. Ці експерименти чітко продемонстрували, що алгоритми аукціону є нижчими до впроваджених алгоритмів найкоротшого шляху для знаходження оптимального рішення^[5].

Хоча в алгоритмі аукціону жодна ітерація ніколи не зменшує загальних вигід (або збільшує, або залишає на тому ж рівні), в альтернативному Угорському алгоритмі (за Куном, 1955, Мункрес, 1957) кожна ітерація покращує результат.

Вважається, що алгоритм аукціону Бертцекаса для знаходження найкоротшого шляху на орієнтованому графі дуже добре справляється у випадку випадкових кривих і у випадку задач з кількома точками призначення^[3].

Див. також

• Алгоритм
• Задача оптимізації

Примітки

1. Bayati, M.; Shah, D.; Sharma, M. (2006). A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm. pp. 557.
2. Resende, Mauricio G. C.; Pardalos, Panos M. (2006), Handbook of optimization in telecommunications, Birkhäuser, ISBN 978-0-387-30662-9, retrieved 10 March 2010
3. Bertsekas, D. P. (1991). «An Auction Algorithm for Shortest Paths». SIAM Journal on Optimization 1 (4): 425
4. «The Parallel Auction Algorithm for Weighted Bipartite Matching», E. Jason Riedy, UC Berkeley, February 2004
5. Larsen, Jesper; Pedersen, Ib (1999). «Experiments with the auction algorithm for the shortest path problem». Nordic J. of Computing 6 (4): 403-42, див. також Larsen, Jesper «A note on the practical performance of the auction algorithm for the shortest path» (1997)

Джерела

• Дімітрі Бертцекас, Стефано Паллотіно та Марія Грація Скутелла Polynomial auction algorithms for shortest paths^{[недоступне посилання]}