C.E. Andrade, R.F. Toso, M.G.C. Resende, and F.K.
Miyazawa
Evolutionary Computation, vol. 23, pp. 279-307, 2015.
ABSTRACT
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
Mauricio G.C. Resende's Home Page
Last modified: 16 September 2015