×

zbMATH — the first resource for mathematics

Heuristics for a bidding problem. (English) Zbl 1086.90062
Summary: We study a bidding problem which can be modeled as a set packing problem. A simulated annealing heuristic with three local moves, including an embedded branch-and-bound move, is developed for the problem. We compared the heuristic with the CPLEX 8.0 solver and the current best non-exact method, Casanova, using the standard CATS benchmark and other realistic test sets. Results show that the heuristic outperforms CPLEX and Casanova.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
91B26 Auctions, bargaining, bidding and selling, and other market models
Software:
CABOB; CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fujishima Y, Leyton-Brown K, Shoham Y. Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. Sixteenth international joint conference on artificial intelligence, 1999, p. 548-53.
[2] Andersson A, Tenhunen M, Ygge F. Integer programming for combinatorial auction winner determination. Proceedings of fourth international conference on multiagent systems, 2000, p. 39-46.
[3] Sandholm, T., Algorithms for optimal winner determination in combinatorial auctions, Artif intell, 135, 1-2, 1-54, (1999) · Zbl 0984.68039
[4] Hoos H, Boutilier C. Solving combinatorial auctions using stochastic local search. Proceedings of the 17th national conference on artificial intelligence, 2000, p. 22-9.
[5] Lau HC, Goh, YG. An intelligent brokering system to support multi-agent web-based 4th-party logistics. Proceedings of the 14th international conference on tools with artificial intelligence, 2002, p. 154-61.
[6] de Vries, S.; Vohra, R., Combinatorial auctionsa survey, INFORMS J comput, 15, 284-309, (2003) · Zbl 1238.91003
[7] Leyton-Brown K, Pearson M, Shoham Y. Towards a universal test suite for combinatorial auction algorithms. ACM conference on electronic commerce, 2000, p. 66-76.
[8] Sandholm T, Suri S, Gilpin A, Levine D. CABOB: a fast optimal algorithm for combinatorial auctions. International joint conferences on artificial intelligence, 2001, p. 1102-8. · Zbl 1232.91329
[9] Guo Y, Lim A, Rodrigues B, Zhu Y. Heuristics for a brokering set packing problem. Proceedings of eighth international symposium on artificial intelligence and mathematics, 2004, p. 10-14.
[10] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[11] Hudson B, Sandholm T. Effectiveness of preference elicitation in combinatorial auctions. AAMAS-02 workshop on agent-mediated electronic commerce (AMEC), 2002, p. 69-86. · Zbl 1024.68742
[12] Schuurmans D, Southey F, Holte RC. The exponentiated subgradient algorithm for heuristic boolean programming. International joint conference on artificial intelligence, 2001, p. 334-41.
[13] Sandholm T, Suri S, Gilpin A, Levine D. Winner determination in combinatorial auction generalizations, 2001. AGENTS-2001 workshop on agent-based approaches to B2B, Montreal, Canada.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.