Biased random-key genetic algorithms for the winner determination
problem in combinatorial auctions

C.E. Andrade, R.F. Toso, M.G.C. Resende, and F.K. Miyazawa

Evolutionary Computation, vol. 23, pp. 279-307, 2015.


In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to  be paid.  We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem.  The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

PDF file of full paper


Go back

Mauricio G.C. Resende's Home Page

Last modified: 16 September 2015