Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.
Author: de Andrade, Carlos Eduardo
Toso, Rodrigo Franco
Resende, Mauricio G C
Miyazawa, Flávio Keidi
Abstract: 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.
Subject: Combinatorial Auctions
Biased Random-key Genetic Algorithms
Genetic Algorithms
Winner Determination Problem
Rights: fechado
Identifier DOI: 10.1162/EVCO_a_00138
Date Issue: 2014
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
pmed_25299242.pdf845.41 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.