Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/243135
Type: Artigo de periódico
Title: Biased Random-key Genetic Algorithms For Thewinner Determination Problem In Combinatorial Auctions
Author: de Andrade
Carlos Eduardo; Toso
Rodrigo Franco; Resende
Mauricio G. C.; Miyazawa
Flavio Keidi
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-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.
Subject: Multidimensional Knapsack-problem
Winner Determination Problem
Evolutionary Algorithms
Heuristics
Country: CAMBRIDGE
Editor: MIT PRESS
Rights: fechado
Identifier DOI: 10.1162/EVCO_a_00138
Address: http://dl.acm.org/citation.cfm?id=2811912
Date Issue: 2015
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000358641000004.pdf1.05 MBAdobe PDFView/Open


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