An efficient local search algorithm for the winner determination problem

Haochen Zhang, Shaowei Cai, Chuan Luo and Minghao Yin ()
Additional contact information
Haochen Zhang: Northeast Normal University
Shaowei Cai: Chinese Academy of Sciences
Chuan Luo: Chinese Academy of Sciences
Minghao Yin: Northeast Normal University

Journal of Heuristics, 2017, vol. 23, issue 5, No 4, 367-396

Abstract: Abstract Combinatorial auction, which allows bidders to bid on combinations of items, is an important type of market mechanism. The winner determination problem (WDP) has extensive applications in combinatorial auctions, and attracts more and more attention due to its strong relevance to business. However, this problem is intractable in theory as it has been proven to be NP-hard, and is also a challenging combinatorial optimization problem in practice. This paper is devoted to designing an efficient heuristic algorithm for solving the WDP. This proposed heuristic algorithm dubbed abcWDP is based on an effective yet simple local search framework, and equipped with three novel strategies, i.e., configuration checking, free-bid exploiting, and pseudo-tie mechanism. Extensive computational experiments on a broad range of benchmarks demonstrate that abcWDP performs much better than state-of-the-art algorithms and CPLEX in terms of both revenue and running time. More encouragingly, our abcWDP algorithm as a sequential algorithm even achieves better computational results than the multi-thread implemented algorithm $$\hbox {CA}_\mathrm{RA}$$ CA RA , which confirms its efficiency.

Keywords: Winner determination problem; Local search; Configuration checking; Pseudo-tie mechanism (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9344-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:23:y:2017:i:5:d:10.1007_s10732-017-9344-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-017-9344-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().