title: Biased Random-Key Genetic Algorithms for the Winner Determination Problem in Combinatorial Auctions.
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.
authors.affiliation: Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852, Brazil andrade@ic.unicamp.br / ce.andrade@gmail.com.
authors.forename: Carlos Eduardo
authors.initials: CE
authors.lastname: de Andrade
authors.affiliation: Department of Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854, USA rtoso@cs.rutgers.edu.
authors.forename: Rodrigo Franco
authors.initials: RF
authors.lastname: Toso
authors.affiliation: Network Evolution Research Department, AT&T Labs Research, 200 S. Laurel Avenue, Middletown, NJ 07748, USA mgcr@research.att.com.
authors.forename: Mauricio G C
authors.initials: MG
authors.lastname: Resende
authors.affiliation: Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852, Brazil fkm@ic.unicamp.br.
authors.forename: Flávio Keidi
authors.initials: FK
authors.lastname: Miyazawa
mesh_terms: D000465:Algorithms; D003132:Commerce / Q000379:methods*; D003198:Computer Simulation; D017059:Models, Econometric
keywords: Combinatorial auctions; biased random-key genetic algorithms; genetic algorithms; winner determination problem