Technical Reports
HPL-2009-163
Click here for full text:
Efficiently Generating k-Best Solutions to Procurement Auctions
Byde, Andrew; Kelly, Terence; Zhou, Yunhong; Tarjan, Robert
HP Laboratories
HPL-2009-163
Keyword(s): procurement, auctions, decision support, combinatorial optimization, knapsack problems, k-shortest paths
Abstract: Procurement executives often find it difficult to articulate their preferences and constraints regarding auctions, making it difficult to cast procurement decisions as straightforward optimization problems. This paper presents an efficient algorithm to aid decision support in such situations. Instead of trying to compute a single optimal solution for the auction winner determination problem, we generate many candidate solutions in ascending order of buyer expenditure. Standard techniques such as clustering and dominance pruning can then trim this list to a compact yet diverse menu of alternatives; other analyses can illuminate the cost of constraints and the competitive landscape. Our efficient solution- generation algorithm addresses sealed-bid procurement auctions with multiple suppliers and multiple types of goods available in multiple units. It supports multi- sourcing and volume discounts/surcharges in bids. Our algorithm may optionally incorporate certain classes of hard constraints, generating only solutions that satisfy them.
17 Pages
Additional Publication Information: Presented at AAIM 2009, San Francisco, June 15, 2009
External Posting Date: July 21, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: July 21, 2009 [Fulltext]