A Lagrangian approach to the winner determination problem in iterative combinatorial reverse auctions

Combinatorial auctions allow allocation of bundles of items to the bidders who value them the most. The NP-hardness of the winner determination problem (WDP) has imposed serious computational challenges when designing efficient solution algorithms. This paper analytically studies the Lagrangian relaxation of WDP and expounds a novel technique for efficiently solving the relaxation problem. Moreover, we introduce a heuristic algorithm that adjusts any infeasibilities from the Lagrangian optimal solution to reach an optimal or a near optimal solution. Extensive numerical experiments illustrate the class of problems on which application of this technique provides near optimal solutions in much less time, as little as a fraction of a thousand, as compared to the CPLEX solver.