Skip to Main content Skip to Navigation
Reports

Discount Auctions for Procuring Hetergeneous Items

Abstract : Advents of business over Internet have given rise to a number of innovative trading mechanisms. In this work we propose a new auction mechanism, called as discount auctions, for procuring heterogeneous items. The buyer, who is the auctioneer, has a unit demand for M distinct items. The suppliers, who are the bidders, specify individual costs for each of the items. In addition, a supplier also specifies a discount function: a non-decreasing function over the number of items. This discount bid, in essence, conveys the individual costs for each of the items and the discount that can be availed based on the number of items bought. The winner determination problem faced by the buyer is to choose the optimal set of winning suppliers and their respective winning items such that the total cost of procurement is minimized. First we show that this problem is NP-hard upon reduction from the set covering problem. Next we propose two exact algorithms to solve the problem to optimality. The first one is a branch-and-bound algorithm, called as branch-on-supply (BoS), which does not use mathematical programming formulation but rather exploits the embedded network structure. The second is a suite of branch-and-cut algorithms. We derive valid inequalities to the integer programming formulation, which serve as cuts for the LP relaxation. A heuristic branching technique, called as branch-on-price (BoP), is proposed that branches on the current price of an item, which is partially supplied by more than one supplier. The design philosophies of the above are different in the sense that BoS searches for the optimal number of items from the suppliers, whereas BoP searches for the optimal price of the items. We compare the performance of these algorithms with extensive computational experiments.
Document type :
Reports
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00122327
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, January 16, 2007 - 10:10:30 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:08:58 PM

Files

Kameshwaran_et_al_2006-New.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00122327, version 2

Citation

Kameshwaran Sampath, Lyès Benyoucef, Xiaolan Xie. Discount Auctions for Procuring Hetergeneous Items. [Research Report] RR-6084, INRIA. 2006, pp.30. ⟨inria-00122327v2⟩

Share

Metrics

Record views

363

Files downloads

285