Abstract
We propose a dedicated tabu search algorithm (TSX_WDP) for the winner determination problem (WDP) in combinatorial auctions. TSX_WDP integrates two complementary neighborhoods designed respectively for intensification and diversification. To escape deep local optima, TSX_WDP employs a backbone-based recombination operator to generate new starting points for tabu search and to displace the search into unexplored promising regions. The recombination operator operates on elite solutions previously found which are recorded in an global archive. The performance of our algorithm is assessed on a set of 500 well-known WDP benchmark instances. Comparisons with five state of the art algorithms demonstrate the effectiveness of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andersson, A., Tenhunen, M., Ygge, F.: Integer programming for combinatorial auction winner determination. In: Proceedings of the 4th International Conference on Multi-agent Systems, pp. 39–46. IEEE Computer Society Press, New York (2000)
Benlic, U., Hao, J.K.: A multilevel memetic approach for improving graph k-partitions. IEEE Trans. Evol. Comput. 15(5), 464–472 (2011)
Boughaci, D., Benhamou, B., Drias, H.: A memetic algorithm for the optimal winner determination problem. Soft. Comput. 13(8–9), 905–917 (2009)
Boughaci, D., Benhamou, B., Drias, H.: Local Search Methods for the optimal winner determination problem in combinatorial auctions. J. Math. Model. Algorithms 9(2), 165–180 (2010)
Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press, Cambridge (2006)
Fujishima, Y., Leyton-Brown, K., Shoham, Y.: Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence, Sweden, pp. 48–53 (1999)
Galinier, P., Hao, J.K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379–397 (1999)
Guo, Y., Lim, A., Rodrigues, B., Zhu, Y.: Heuristics for a bidding problem. Comput. Oper. Res. 33(8), 2179–2188 (2006)
Holland, A., O’sullivan, B.: Towards fast Vickrey pricing using constraint programming. Artif. Intell. Rev. 21(3–4), 335–352 (2004)
Hoos, H.H., Boutilier, C.: Solving combinatorial auctions using stochastic local search. In: Proceedings of the 17th National Conference on Artificial Intelligence, USA, pp. 22–29 (2000)
Abrache, J., Crainic, T.G., Gendreau, M., Rekik, M.: Combinatorial auctions. Ann. Oper. Res. 153(1), 131–164 (2007)
Klemperer, P.: Auctions: Theory and Practice. Princeton University Press, Princeton (2004)
Lau, H.C., Goh, Y.G.: An intelligent brokering system to support multi-agent web-based 4th-party logistics. In: Proceedings of the 14th International Conference on Tools with Artificial Intelligence, Washington, DC, pp. 54–61 (2002)
Lehmann, D., Rudolf, M., Sandholm, T.: The winner determination problem. In: Cramton, P., et al. (eds.) Combinatorial Auctions. MIT Press, Cambridge (2006)
Leyton-Brown, K., Shoham, Y., Tennenholtz, M.: An algorithm for multi-unit combinatorial auctions. In: Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence, Austin, Texas, pp. 56–61. AAAI Press/MIT Press (2000)
Nisan, N.: Bidding and allocation in combinatorial auctions. In: Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 1–12. ACM Press, Minneapolis (2000)
Rothkopf, M.H., Pekee, A., Ronald, M.: Computationally manageable combinatorial auctions. Manage. Sci. 44(8), 1131–1147 (1998)
Sandholm, T.: Optimal winner determination algorithms. In: Cramton, P., et al. (eds.) Combinatorial Auctions. MIT Press, Cambridge (2006)
Sandholm, T., Suri, S.: Improved optimal algorithm for combinatorial auctions and generalizations. In: Proceedings of the 17th National Conference on Artificial Intelligence, USA, pp. 90–97 (2000)
Sandholm, T., Suri, S., Gilpin, A., Levine, D.: CABoB: a fast optimal algorithm for combinatorial auctions. In: Proceedings of the International Joint Conferences on Artificial Intelligence, Seattle, WA, pp. 1102–1108 (2001)
Vries, S., Vohra, R.: Combinatorial auctions a survey. INFORMS J. Comput. 15, 284–309 (2003)
Wang, Y., Lu, Z., Glover, F., Hao, J.K.: Backbone guided tabu search for solving the UBQP problem. J. Heuristics 19(4), 679–695 (2013)
Acknowledgment
We are grateful to the referees for their comments and questions which helped us to improve the paper. The work is partially supported by the RaDaPop (2009–2013) and LigeRO projects (2009–2013) from the Region of Pays de la Loire, France.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Sghir, I., Hao, JK., Ben Jaafar, I., Ghédira, K. (2014). A Recombination-Based Tabu Search Algorithm for the Winner Determination Problem . In: Legrand, P., Corsini, MM., Hao, JK., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2013. Lecture Notes in Computer Science(), vol 8752. Springer, Cham. https://doi.org/10.1007/978-3-319-11683-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-11683-9_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11682-2
Online ISBN: 978-3-319-11683-9
eBook Packages: Computer ScienceComputer Science (R0)