خوارزمية المزاد

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
الموسوعة الحرة

يُطلق مصطلح " خوارزمية المزاد " [ 1 ] على عدة أنواع من خوارزميات التحسين التوافقي التي تحل مسائل التخصيص ، ومسائل تحسين الشبكات ذات التكلفة الخطية والمحدبة/غير الخطية. وقد استُخدمت خوارزمية المزاد في مجال الأعمال لتحديد أفضل الأسعار لمجموعة من المنتجات المعروضة على عدة مشترين. وهي عملية تكرارية، لذا فإن اسم "خوارزمية المزاد" مرتبط بمزاد البيع ، حيث تُقارن عروض أسعار متعددة لتحديد أفضل عرض، وتُباع المنتجات في النهاية لأصحاب أعلى الأسعار.

يُعد الشكل الأصلي لخوارزمية المزاد طريقةً تكراريةً لإيجاد الأسعار المثلى وتخصيص يُعظّم صافي الفائدة في رسم بياني ثنائي الأجزاء ، وهي مسألة مطابقة الوزن الأقصى (MWM). [ 2 ] [ 3 ] وقد اقترح ديمتري بيرتسيكاس هذه الخوارزمية لأول مرة عام 1979.

تُعدّ أفكار خوارزمية المزاد وتوسيع النطاق ε [ 1 ] أساسيةً أيضًا في خوارزميات الدفع المسبق لمشاكل تدفق الشبكة الخطية أحادية السلعة. في الواقع، يمكن اشتقاق خوارزمية الدفع المسبق لمشكلة التدفق الأقصى بتطبيق خوارزمية المزاد الأصلية لعام 1979 على مشكلة التدفق الأقصى بعد إعادة صياغتها كمشكلة تخصيص. علاوة على ذلك، فإن خوارزمية الدفع المسبق لمشكلة التدفق الخطي ذي التكلفة الدنيا تُكافئ رياضيًا طريقة الاسترخاء ε، والتي يتم الحصول عليها بتطبيق خوارزمية المزاد الأصلية بعد إعادة صياغة المشكلة كمشكلة تخصيص مكافئة. [ 4 ]

A later variation of the auction algorithm that solves shortest path problems was introduced by Bertsekas in 1991.[5] It is a simple algorithm for finding shortest paths in a directed graph. In the single origin/single destination case, the auction algorithm maintains a single path starting at the origin, which is then extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable will be adjusted at each iteration, in order to either improve or maintain the value of a dual function. In the case of multiple origins, the auction algorithm is well-suited for parallel computation.[5] The algorithm is closely related to auction algorithms for other network flow problems.[5] According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella, Polynomial Auction Algorithms for Shortest Paths.

Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite matching, described by E. Jason Riedy in 2004.[6]

Comparisons

The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers.[7] Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution of single-origin to all-destinations problems.[7]

Although with the auction algorithm the total benefit is monotonically increasing with each iteration, in the Hungarian algorithm (from Kuhn, 1955; Munkres, 1957) the total benefit strictly increases with each iteration.

The auction algorithm of Bertsekas for finding shortest paths within a directed graph is reputed to perform very well on random graphs and on problems with few destinations.[5]

See also

References

  1. 12Dimitri P. Bertsekas. "A distributed algorithm for the assignment problem", original paper, 1979.
  2. ↑M.G. Resende, P.M. Pardalos. "Handbook of optimization in telecommunications", 2006
  3. ↑ م. بياتي، د. شاه، م. شارما. "خوارزمية مطابقة الوزن الأقصى للمنتج الأقصى المبسطة وخوارزمية المزاد"، 2006، صفحة ويب PDF: MIT-bpmwm-PDF مؤرشفة في 2017-09-21 في Wayback Machine .
  4. ↑ بيرتسيكاس، ديمتري (ديسمبر 1986). "أساليب الاسترخاء الموزعة لمشاكل تدفق الشبكة الخطية". المؤتمر الخامس والعشرون لمعهد مهندسي الكهرباء والإلكترونيات حول التحكم واتخاذ القرارات . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 2101-2106 . doi : 10.1109/cdc.1986.267433 . 
  5. 1 2 3 4 ديمتري ب. بيرتسيكاس. "خوارزمية مزاد لأقصر المسارات"، مجلة SIAM للتحسين ، 1: 425-447، 1991، PSU-bertsekas91auction
  6. ↑ "خوارزمية المزاد المتوازي للمطابقة الثنائية الموزونة"، إي. جيسون ريدى، جامعة كاليفورنيا في بيركلي، فبراير 2004،.
  7. 1 2 لارسن، جيسبر؛ بيدرسن، إيب (1999). "تجارب مع خوارزمية المزاد لمسألة أقصر مسار" . المجلة الإسكندنافية للحوسبة . 6 (4): 403-442 . ISSN 1236-6064 . انظر أيضًا ملاحظة حول الأداء العملي لخوارزمية المزاد لأقصر مسار مؤرشف في 2011-06-05 في Wayback Machine (1997) بواسطة المؤلف الأول.
  • ديمتري ب. بيرتسيكاس. "تحسين الشبكة الخطية"، مطبعة معهد ماساتشوستس للتكنولوجيا، 1991، على الإنترنت .
  • ديمتري ب. بيرتسيكاس. "تحسين الشبكة: النماذج المستمرة والمتقطعة"، أثينا ساينتيفيك، 1998 .
  • ديمتري ب. بيرتسيكاس. "خوارزمية مزاد لأقصر المسارات"، مجلة SIAM للتحسين ، 1:425-447، 1991، صفحة الويب: PSU-bertsekas91auction .
  • DP Bertsekas, S. Pallottino, MG Scutella. "خوارزميات المزاد متعددة الحدود لأقصر المسارات،" التحسين الحسابي والتطبيقات ، المجلد 4، 1995، ص 99-125.
  • تطبيق خوارزمية مزاد بيرتسيكاس في ماتلاب بواسطة فلوريان برنارد، صفحة الويب: تبادل ملفات ماتلاب .