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....[ Read more ]

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.