HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Industrial Engineering and Logistics Management >
IELM Master Theses  >

Please use this identifier to cite or link to this item:
Title: A Lagrangian heuristic for winner determination problem in combinatorial auctions
Authors: Tang, Jiqing
Issue Date: 2004
Abstract: We model the Winner Determination in Combinatorial Auctions as an NP-Complete maximization Set Packing problem. A Lagrangian-based Heuristic LAHA is proposed for this problem. The key features of our algorithm include classical subgradient optimization, stochastic bid selection and dynamic column fixing. A number of different bid ordering rules are used in our heuristic. Moreover, an effective local search refinement procedure is presented at the end of the algorithm. We also propose a new methodology PBP to produce realistic test problems which are computationally more difficult than CATS generated benchmarks. We tested LAHA on 238 problems of 13 different distributions and compared the computational results against the state-of-the-art IP solver CPLEX 8.0 and a recent heuristic SAGII. LAHA achieved a result in 90 seconds for all the problems we solved and it was especially efficient with large-scale hard problems. Among the 146 problems for which the optimum is known, LAHA found the optimum in 91 cases and produced on average 99.2% optimal solutions for the rest. Moreover, on the other 92 hard problems for which the optimum is not known, LAHA's solutions were on average 2% better than the solutions generated by CPLEX in the time frame of 30 minutes.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2004
xiii, 74 leaves : ill. ; 30 cm
HKUST Call Number: Thesis IEEM 2004 Tang
Appears in Collections:IELM Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.