A Lagrangian heuristic for winner determination problem in combinatorial auctions

We present a Lagrangian-based heuristic LAHA for the Winner Determination Problem in Combinatorial Auctions. The algorithm makes use of the market computing power by applying subgradient optimization with variable fixing. A number of different bid ordering and selection rules are used in our heuristic. Moreover, an effective local search refinement procedure is presented at the end of our algorithm. We propose a new methodology PBP to produce realistic test problems which are computationally more difficult than CATS generated benchmarks. LAHA was tested on 238 problems of 13 different distributions. Among the 146 problems for which the optimum is known, LAHA found the optimum in 91 cases and produce 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 8.0 in 30 minutes