Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896609 | European Journal of Operational Research | 2015 | 32 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Bahareh Mansouri, Elkafi Hassini,