基於組合式反向拍賣的高效能演算法

A Lagrangian Relaxation Approach For Combinatorial Reverse Auction

蔡世民(Shih-Min Tsai)

指導教授 ： 謝富雄

朝陽科技大學/資訊學院/資訊工程系/碩士(2009年)

摘要

近年來網路拍賣的市場不斷成長，已經成為電子商務相當重要的一種商業模式。現今許多的拍賣網站都只能對單一商品進行競標，組合式競標，讓參與者可以在單一次的拍賣活動中同時對多樣商品進行投標，改善了傳統只能針對單一商品進行競標的效率。組合式競標是使眾多的競標者都能夠在一次的拍賣過程中，依照自己的喜愛、偏好，針對不同的商品組合去競標。他們能夠一次選取多樣物品，並且給予這些物品的組合一個金額。反向拍賣是將拍賣模式應用在採購商品的一種商業模式，目的在讓買方以最低的價格同時採購到所需求的多樣商品。在本篇文章中，我們將會提出一個反向拍賣的模式，為了解決最佳化分配問題和NP-complete的問題，我們使用了Lagrangian relaxation的方法，然後運用subgradient最佳化技術去做調整，讓最佳化問題能夠以有效率地尋找到近似解及數據的統計。

關鍵字

獲勝者決策問題 ； 組合式競標 ； 拉格朗日 ； NP問題

並列摘要

Auction is a kind of important business model for e-commerce. Combinatorial reverse auction can be applied in procurement to purchase goods at the lowest possible cost if there is complementarity or substitutability between the goods. A buyer can hold a reverse auction to try to obtain the goods from a set of sellers who can provide the goods. Each seller places bids for each bundle of goods he can provide. Although combinatorial reverse auction has attracted much attention recently, design of effective mechanism to guide the bidders to modify or submit their bids to collectively find a feasible solution requires further study. The problem is to determine the winners. In this paper, we consider a winner determination problem in which a buyer wants to acquire items from a set of sellers to process the task on hand. The task requires a minimal set of items for executing the operations. Each seller owns a set of items to bid for the task. The problem is to determine the winners to minimize the total cost to acquire the required items. The main results include: (1) a problem formulation for the combinatorial reverse auction problem; (2) a solution methodology based on Lagrangian relaxation; (3) an economic interpretation and (4) specification of the requirements for the implementation of our solution algorithms.

並列關鍵字

Lagrangian relaxation ； Combinatorial Auctions ； Winner determination ； NP-complete

參考文獻

[1] Ali Haydar Özer, Can Özturan (2007), A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction, Computers & Operations Research 36 (2009) 196 – 208.

[2] Aiying Rong, Risto Lahdelma, Peter B. Luh(2008), Lagrangian relaxation based algorithm for trigeneration planning with storages ,European Journal of Operational Research, Volume 188, Issue 1, 1 July 2008, Pages 240-257

[3] Chia-Ho Chen, Ching-Jung Ting(2007), Combining Lagrangian heuristic and Ant Colony System to solve the Single Source Capacitated Facility Location Problem, Transportation Research Part E: Logistics and Transportation Review, Volume 44, Issue 6, November 2008, Pages 1099-1122.

[5] Huiye Ma, Ho-fung Leung(2005), Adaptive soft bid determination in bidding strategies for continuous double auctions, Tools with Artificial Intelligence, 2005. ICTAI 05. 17th IEEE International Conference on 14-16 Nov. 2005 Page(s):5 pp.

[6] Iglesias, O. Ribeiro, R.A. Fonseca, J.R.(2004), A Fuzzy Multi-Agent Bidding Model, ntelligent Agent Technology, 2004. (IAT 2004). Proceedings. IEEE/WIC/ACM International Conference on 2004 Page(s):517 – 520.