Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Biased Random-Key Genetic Algorithms for theWinner Determination Problem in Combinatorial Auctions

Texto completo
Autor(es):
de Andrade, Carlos Eduardo [1] ; Toso, Rodrigo Franco [2] ; Resende, Mauricio G. C. [3] ; Miyazawa, Flavio Keidi [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 - USA
[3] AT&T Labs Res, Network Evolut Res Dept, Middletown, NJ 07748 - USA
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: EVOLUTIONARY COMPUTATION; v. 23, n. 2, p. 279-307, SUM 2015.
Citações Web of Science: 6
Resumo

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-pricemodel. 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 thatmakes 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. (AU)

Processo FAPESP: 10/05233-5 - Algoritmos evolutivos para alguns problemas em telecomunicações
Beneficiário:Carlos Eduardo de Andrade
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 12/08222-0 - Algoritmos para determinação de vencedores e precificação em leilões combinatóriais
Beneficiário:Carlos Eduardo de Andrade
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado