{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:45:55Z","timestamp":1760708755296},"reference-count":60,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1162\/evco_a_00138","type":"journal-article","created":{"date-parts":[[2014,10,9]],"date-time":"2014-10-09T18:56:42Z","timestamp":1412881002000},"page":"279-307","source":"Crossref","is-referenced-by-count":17,"title":["Biased Random-Key Genetic Algorithms for the Winner Determination Problem in Combinatorial Auctions"],"prefix":"10.1162","volume":"23","author":[{"given":"Carlos Eduardo","family":"de Andrade","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852, Brazil \/"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo Franco","family":"Toso","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mauricio G. C.","family":"Resende","sequence":"additional","affiliation":[{"name":"Network Evolution Research Department, AT&T Labs Research, 200 S. Laurel Avenue, Middletown, NJ 07748, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fl\u00e1vio Keidi","family":"Miyazawa","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","first-page":"63","author":"Alaya I.","year":"2004","journal-title":"Proceedings of the International Conference on Bioinspired Optimization Methods and their Applications (BIOMA 2004)"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1145\/2463372.2463434"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598284"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.154"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1995.tb02031.x"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s12599-008-0014-3"},{"key":"B7","first-page":"189","volume-title":"Combinatorial auctions","author":"Bikhchandani S.","year":"2006"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02538-9_13"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481.013"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29694-9_29"},{"key":"B11","first-page":"13:905","author":"Boughaci D.","year":"2009","journal-title":"Soft Computing"},{"key":"B12","first-page":"4:434","author":"Boyer V.","year":"2010","journal-title":"European Journal of Industrial Engineering"},{"key":"B13","first-page":"2:65","author":"Buer T.","year":"2010","journal-title":"Logistics Research"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.01.007"},{"key":"B15","first-page":"30","volume":"2037","author":"Chardaire P.","year":"2001","journal-title":"Applications of Evolutionary Computing, Evo Workshops 2001"},{"key":"B16","first-page":"4:63","author":"Chu P. C.","year":"1998","journal-title":"Journal of Heuristics"},{"key":"B17","author":"Conover W. J.","year":"1980","journal-title":"Practical nonparametric statistics"},{"key":"B18","author":"Cramton P.","year":"2006","journal-title":"Combinatorial auctions"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060681"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2008.10.009"},{"key":"B22","first-page":"4:1","author":"Fay M. P.","year":"2010","journal-title":"Statistics Surveys"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a011"},{"key":"B24","first-page":"47:424","author":"Fredman M. L.","year":"1993","journal-title":"Journal of Computer and System Sciences"},{"key":"B25","volume-title":"Computers and intractability: A guide to the theory of np-completeness","author":"Garey M. R.","year":"1979"},{"key":"B26","volume-title":"Genetic algorithms in search, optimization and machine learning","author":"Goldberg D. E","year":"1989"},{"key":"B27","first-page":"64:275","author":"Gomory R. E.","year":"1958","journal-title":"Bulletin of the American Mathematical Society"},{"key":"B28","first-page":"17:487","author":"Gon\u00e7alves J. F.","year":"2011","journal-title":"Journal of Heuristics"},{"key":"B29","first-page":"22:180","author":"Gon\u00e7alves J. F.","year":"2011","journal-title":"Journal of Combinatorial Optimization"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.007"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"B32","first-page":"57","volume":"2056","author":"Holte R.","year":"2001","journal-title":"Advances in Artificial Intelligence, AI 2001"},{"key":"B33","first-page":"22","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence","author":"Hoos H. H.","year":"2000"},{"key":"B34","author":"Krishna V.","year":"2010","journal-title":"Auction theory"},{"key":"B35","first-page":"154","volume-title":"Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence","author":"Lau H. C.","year":"2002"},{"key":"B36","first-page":"49:577","author":"Lehmann D.","year":"2002","journal-title":"Journal of the ACM"},{"key":"B38","author":"L\u00f3pez-Ib\u00e1\u00f1ez M.","year":"2011","journal-title":"Technical Report TR\/IRIDIA\/2011-004, IRIDIA, Universit\u00e9 Libre de Bruxelles"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1110.0460"},{"key":"B40","first-page":"8:3","author":"Matsumoto M.","year":"1998","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352872"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199903)46:2<199::AID-NAV5>3.0.CO;2-L"},{"key":"B45","first-page":"5:199","author":"Padberg M. W.","year":"1973","journal-title":"Mathematical Programming"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1145\/1883612.1883617"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1145\/1276958.1277258"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0344"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1145\/335527.335530"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666886"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1131"},{"key":"B53","first-page":"10:75","author":"Rothlauf F.","year":"2002","journal-title":"Evolutionary Computation"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00159-X"},{"key":"B55","first-page":"337","author":"Sandholm T.","year":"2006","journal-title":"Combinatorial auctions"},{"key":"B56","first-page":"1588","volume":"3","author":"Schwind M.","year":"2003","journal-title":"Congress on Evolutionary Computation"},{"key":"B57","first-page":"230","volume-title":"Proceedings of the 4th International Conference on Genetic Algorithms","author":"Spears W. M.","year":"1991"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2014.890197"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.01.024"},{"key":"B60","first-page":"7:33","author":"Whitley D.","year":"1998","journal-title":"Journal of Computing and Information Technology"},{"key":"B61","volume-title":"Integer programming","author":"Wolsey L. A","year":"1998"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:35Z","timestamp":1615586315000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/23\/2\/279-307\/989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1162\/EVCO_a_00138"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00138","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}