×

An effective discrete dynamic convexized method for solving the winner determination problem. (English) Zbl 1404.91126

Summary: The winner determination problem (WDP) arises in combinatorial auctions. It is known to be NP-hard. In this paper, we propose a discrete dynamic convexized method for solving this problem. We first propose an adaptive penalty function to convert the WDP into an equivalent unconstrained integer programming problem. Based on the structure of the WDP, we construct an unconstrained auxiliary function, which is maximized iteratively using a local search and is updated whenever a better maximizer is found. By increasing the value of a parameter in the auxiliary function, the maximization of the auxiliary function can escape from previously converged local maximizers. To evaluate the performance of the dynamic convexized method, extensive experiments were carried out on realistic test sets from the literature. Computational results and comparisons show that the proposed algorithm improved the best known solutions on a number of benchmark instances.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
90C10 Integer programming

Software:

CABOB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abrache J, Crainic TG, Gendreau M (2005) Models for bundle trading in financial markets. Eur J Oper Res 160(1):88-105 · Zbl 1067.90094 · doi:10.1016/j.ejor.2003.06.022
[2] Ali MM, Zhu WX (2013) A penalty function-based differential evolution algorithm for constrained global optimization. Comput Optim Appl 54(3):707-739 · Zbl 1295.90050 · doi:10.1007/s10589-012-9498-3
[3] Andersson A, Tenhunen M, Ygge F (2000) Integer programming for combinatorial auction winner determination. In: Proceedings of 4th international conference on multi-agent system, IEEE computer Society Press, New York, pp 39-46 · Zbl 1156.65065
[4] Avasarala V, Mullen T, Hall DL, Garga A (2005) MASM: a market architecture or sensor management in distributed sensor networks. In: SPIE Defense and Security Symposium, Orlando FL, pp 5813-5830 · Zbl 0989.90094
[5] Avasarala V, Pllavarapu H, Mullen T (2006) An approximate algorithm for resource allocation using combinatorial auctions. In: International Conference on Intelligent Agent Technology, pp 571-578
[6] Ball, M.; Donohue, G.; Hoffman, K.; Steinberg, R. (ed.); Cramton, P. (ed.); Shoham, Y. (ed.), Auctions for the safe, efficient and equitable allocation of airspace system resources, No. 22 (2006), Cambridge
[7] Boughaci D (2013) Metaheuristic approaches for the winner determination problem in combinatorial auction. Artif Intell Evolut Comput Metaheuristics 427:775-791 · Zbl 1277.90151 · doi:10.1007/978-3-642-29694-9_29
[8] Boughaci D, Benhamou B, Drias H (2009) A memetic algorithm for the optimal winner determination problem. Soft Comput 13(8-9):905-917 · doi:10.1007/s00500-008-0355-3
[9] de Vries S, Vohra R (2003) Combinatorial auctions: a survey. INFORMS J Comput 15(3):284-309 · Zbl 1238.91003 · doi:10.1287/ijoc.15.3.284.16077
[10] Escudero LF, Landete M, Marín A (2009) A branch-and-cut algorithm for the winner determination problem. Decis Support Syst 46(3):649-659 · doi:10.1016/j.dss.2008.10.009
[11] Fiduccia CM, Mattheyses RM (1982) A linear time heuristic for improving network partitions. In: Proceedings of 19th ACM/IEEE Design Automation Conference, Las Vegas, NV, pp 175-181 · Zbl 1277.90151
[12] Fuishima Y, Leyton-Brown K, Shoham Y (1999) Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In: Sixteenth International Joint Conference on Artificial Intelligence, pp 48-53
[13] Guo Y, Lim A, Rodrigues B, Zhu Y (2006) Heuristics for a bidding problem. Comput Oper Res 33(8):2179-2188 · Zbl 1086.90062 · doi:10.1016/j.cor.2005.01.007
[14] Halldórsson MM (2000) Approximations of weighted independent set and hereditary subset problems. J Graph Algorithms Appl 4(1):1-16 · Zbl 0952.05069 · doi:10.7155/jgaa.00020
[15] Hoos HH, Boutilier C (2000) Solving combinatorial auctions using stochastic local search. In: Proceedings of the 17th National Conference on Artificial Intelligence, pp 22-29
[16] Lau HC, Goh YG (2002) An intelligent brokering system to support multi-agent 4th-party logistics. In: Proceedings of the 14th International Conference on Tools with Artificial Intelligence, pp 154-161
[17] Leyton-Brown K, Pearson M, Shoham Y (2000) Towards a universal test suite for combinatorial auction algorithms. In: ACM Conference on Electronic Commerce, pp 66-76 · Zbl 1160.90598
[18] Leyton-Brown K, Tennenholtz M, Shoham Y (2000) An algorithm for multi-unit combinatorial auctions. In: Proceedings of the 17th National Conference on Artificial Intelligence, Austin, Gemes-2000, Bilbao, and ISMP-2000, Atlanta, pp 56-61 · Zbl 0984.68039
[19] Lin G, Zhu WX (2012) A discrete dynamic convexized method for the max-cut problem. Ann Oper Res 196(1):371-390 · Zbl 1269.90130 · doi:10.1007/s10479-012-1133-2
[20] Lü Z, Hao JK (2010) A memetic algorithm for graph coloring. Eur J Oper Res 203(1):241-250 · Zbl 1176.90610 · doi:10.1016/j.ejor.2009.07.016
[21] Mito M, Fujita S (2004) On heuristics for solving winner determination problem in combinatorial auctions. J Heuristics 10(5):507-523 · Zbl 1090.91034 · doi:10.1023/B:HEUR.0000045322.51784.2a
[22] Mullen T, Avasarala V, Hall DL (2006) Customer-driven sensor management. IEEE Intell Syst 21(2):41-49 · doi:10.1109/MIS.2006.23
[23] Rothkopf MH, Pekee A, Ronald M (1998) Computationally manageable combinatorial auctions. Manage Sci 44(8):1131-1147 · Zbl 0989.90094 · doi:10.1287/mnsc.44.8.1131
[24] Sandholm T (2002) Algorithms for optimal winner determination in combinatorial auctions. Artif Intell 135(1-2):1-54 · Zbl 0984.68039 · doi:10.1016/S0004-3702(01)00159-X
[25] Sandholm T, Suri S (2000) Improved optimal algorithm for combinatorial auctions and generalizations. In: Proceedings of the 17th National Conference on Artificial Intelligence, pp 90-97 · Zbl 0952.05069
[26] Sandholm T, Suri S, Gilpin A, Levine D (2001) CABoB: a fast optimal algorithm for combinatorial auctions. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp 1102-1108 · Zbl 1232.91329
[27] Shil SK, Mouhoub M, Sadaoui S (2013) Winner determination in combinatorial reverse auctions. Contemp Chall Solut Appl Artif Intell 489:35-40 · doi:10.1007/978-3-319-00651-2_5
[28] Walsh WE, Wellman M, Ygge F (2000) Combinatorial auctions for supply chain formation. In: ACM Conference on Electronic Commerce, pp 260-269 · Zbl 1176.90610
[29] Zhu WX, Ali MM (2009) Discrete dynamic convexized method for nonlinearly constrained integer programming. Comput Oper Res 36(10):2723-2728 · Zbl 1160.90598 · doi:10.1016/j.cor.2008.12.002
[30] Zhu WX, Fan H (2009) A discrete dynamic convexized method for nonlinear integer programming. J Comput Appl Math 223(1):356-373 · Zbl 1156.65065 · doi:10.1016/j.cam.2008.01.023
[31] Zhu WX, Lin G (2011) A dynamic convexized method for nonconvex mixed integer nonlinear programming. Comput Oper Res 38(12):1792-1804 · Zbl 1215.90047 · doi:10.1016/j.cor.2011.02.014
[32] Zhu WX, Lin G, Ali MM (2013) Max-k-cut by the discrete dynamic convexized method. INFORMS J Comput 25(1):27-40 · doi:10.1287/ijoc.1110.0492
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.