Алгоритм аукциона - Auction algorithm

Не путать с Алгоритм аукциона.

Период, термин "алгоритм аукциона"[1] применяется к нескольким вариациям комбинаторная оптимизация алгоритм который решает проблемы с назначением, а также задачи оптимизации сети с линейной и выпуклой / нелинейной стоимостью. An алгоритм аукциона используется в деловой среде для определения лучших цен на набор продуктов, предлагаемых нескольким покупателям. Это итеративная процедура, поэтому название «алгоритм аукциона» связано с продажей аукцион, где сравниваются несколько ставок, чтобы определить лучшее предложение, при этом окончательные продажи достаются тем, кто предложил самую высокую цену.

Первоначальная форма алгоритма аукциона представляет собой итерационный метод поиска оптимальных цен и назначение, которое максимизирует чистую прибыль в двудольный граф, то соответствие максимального веса проблема (MWM).[2][3]Этот алгоритм был впервые предложен Димитрий Берцекас в 1979 г.

Идеи алгоритма аукциона и ε-масштабирования[1] также занимают центральное место в алгоритмах проталкивания предпотока для задач линейного сетевого потока для одного товара. Фактически алгоритм проталкивания предпотока для максимального потока может быть получен путем применения исходного алгоритма аукциона 1979 года к задаче максимального потока после переформулирования как задачи присваивания. Более того, алгоритм проталкивания перед потоком для линейной задачи потока с минимальной стоимостью математически эквивалентен методу ε-релаксации, который получается путем применения исходного алгоритма аукциона после того, как проблема переформулирована как эквивалентная задача назначения.[4]

Более поздний вариант алгоритма аукциона, который решает проблемы кратчайшего пути был представлен Бертсекасом в 1991 году.[5]Это простой алгоритм поиска кратчайших путей в ориентированный граф. В случае единственного источника / единственного места назначения алгоритм аукциона поддерживает единственный путь, начинающийся в источнике, который затем расширяется или сокращается одним узлом на каждой итерации. Одновременно на каждой итерации будет корректироваться не более одной двойной переменной, чтобы улучшить или сохранить значение двойной функции. В случае множественного происхождения алгоритм аукциона хорошо подходит для параллельных вычислений.[5] Алгоритм тесно связан с алгоритмами аукционов для других задач сетевого потока.[5] Согласно вычислительным экспериментам, алгоритм аукциона обычно уступает другим современным алгоритмам для задачи кратчайшего пути для всех пунктов назначения, но очень быстр для задач с небольшим числом пунктов назначения (существенно больше одного и существенно меньше общего числа пунктов назначения). узлов); см. статью Бертсекаса, Паллоттино и Скутеллы, Алгоритмы полиномиального аукциона для поиска кратчайших путей.

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

Сравнения

Алгоритмы (последовательных) аукционов для задачи поиска кратчайшего пути были предметом экспериментов, о которых сообщалось в технических статьях.[7] Эксперименты ясно показывают, что алгоритм аукциона уступает современным алгоритмам поиска кратчайшего пути для поиска оптимального решения задач от одного источника до всех пунктов назначения.[7]

Хотя с алгоритмом аукциона общая выгода монотонно возрастающий с каждой итерацией в Венгерский алгоритм (из Kuhn, 1955; Munkres, 1957) общая выгода строго увеличивается с каждой итерацией.

Алгоритм аукциона Бертсекаса для поиска кратчайших путей в ориентированном графе имеет хорошую репутацию на случайных графах и задачах с небольшим количеством пунктов назначения.[5]

Смотрите также

Рекомендации

  1. ^ а б Дмитрий Петрович Берцекас. «Распределенный алгоритм для задачи о назначении», оригинальная статья, 1979 г..
  2. ^ М.Г. Ресенде, П. Пардалос. «Справочник по оптимизации в телекоммуникациях», 2006
  3. ^ М. Баяти, Д. Шах, М. Шарма. "Более простой алгоритм согласования максимального веса максимального продукта и алгоритм аукциона", 2006 г., веб-страница в формате PDF: MIT-bpmwm-PDF В архиве 2017-09-21 в Wayback Machine.
  4. ^ Дмитрий Петрович Бертсекас. "Распределенные алгоритмы релаксации для линейных задач сетевого потока", Proc. 25-го IEEE CDC, Афины, Греция, 1986, стр. 2101-2106, онлайн из IEEEXplore [1]
  5. ^ а б c d Дмитрий Петрович Бертсекас. «Алгоритм аукциона по кратчайшим путям», SIAM Journal по оптимизации, 1:425—447, 1991,PSU-bertsekas91аукцион
  6. ^ «Алгоритм параллельного аукциона для взвешенного двустороннего сопоставления», Э. Джейсон Риди, Калифорнийский университет в Беркли, февраль 2004 г., [2].
  7. ^ а б Ларсен, Джеспер; Педерсен, Иб (1999). «Эксперименты с алгоритмом аукциона для задачи кратчайшего пути». Северный вычислительный журнал. 6 (4): 403–42. ISSN  1236-6064., смотрите также Примечание о практической работе алгоритма аукциона по кратчайшему пути В архиве 2011-06-05 на Wayback Machine (1997) первого автора.

внешняя ссылка