Title :
Combinatorial Reverse Auction Based on Lagrangian Relaxation
Author :
Hsieh, Fu-Shiung ; Tsai, Shih-Min
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Chaoyang Univ. of Technol., Taichung
Abstract :
In procurement, a buyer who wants to obtain some goods at the lowest possible cost can hold a reverse auction to try to obtain the goods from a set of sellers who can provide the goods. If there is complementarity or substitutability between the goods, a combinatorial reverse auction can be beneficial. Each seller places bids for each bundle of goods he can provide. 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.
Keywords :
combinatorial mathematics; commerce; minimisation; relaxation theory; Lagrangian relaxation; combinatorial reverse auction problem; economic interpretation; minimal item set; procurement; requirement specification; total cost minimization; winner determination problem; Chaos; Chaotic communication; Computer science; Costs; FCC; Iterative algorithms; Lagrangian functions; Licenses; Marketing and sales; Procurement; Lagrangian relaxation; combinatorial auction; reverse auction;
Conference_Titel :
Asia-Pacific Services Computing Conference, 2008. APSCC '08. IEEE
Conference_Location :
Yilan
Print_ISBN :
978-0-7695-3473-2
Electronic_ISBN :
978-0-7695-3473-2
DOI :
10.1109/APSCC.2008.112