Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home

Technical Reports


HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

Generating k Best Solutions to Winner Determination Problems: Algorithms & Application to Procurement

Kelly, Terence; Byde, Andrew


Keyword(s): auctions; procurement; knapsack problems; k-shortest paths; decision support; preference elicitation

Abstract: Auction participants often cannot easily articulate their requirements and preferences. The buyer in a procurement auction, for instance, may hesitate to quantify the value of non-price solution attributes, and she may have difficulty delineating between hard and soft constraints. Consequently it can be difficult to formulate the winner determination problem (WDP) as a straightforward optimization problem. Existing decision-support aids for such situations, including scenario navigation and preference elicitation, address this difficulty through extensions to an optimization framework. This paper presents a complementary approach that frames the procurement decision problem as one of exploration rather than optimization. The foundation of our approach is an algorithm that generates k best solutions to auction WDPs. Our algorithm can scale to practical problem sizes for an interesting class of procurement auctions, and furthermore can incorporate hard constraints into the generation process. We describe ways of extracting useful guidance for the decision- maker from k-cheapest WDP solutions. We evaluate our method using real bids submitted by real suppliers in an HP material parts procurement auction.

10 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.