Optimization Heuristics for the Combinatorial Auction Problem


Schwind, Michael ; Stockheim, Tim ; Rothlauf, Franz


[img]
Preview
PDF
heinzl13.pdf - Published

Download (297kB)

URL: https://ub-madoc.bib.uni-mannheim.de/90
URN: urn:nbn:de:bsz:180-madoc-906
Document Type: Working paper
Year of publication: 2003
The title of a journal, publication series: Working papers
Volume: 13
Place of publication: Mannheim
Publication language: English
Institution: Business School > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC publication series: Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Subject: 004 Computer science, internet
Subject headings (SWD): Algorithmus
Abstract: This paper presents and compares three heuristics for the combinatorial auction problem. Besides a simple greedy (SG) mechanism, two metaheuristics, a simulated annealing (SA), and a genetic algorithm (GA) approach are developed which use the combinatorial auction process to find an allocation with maximal revenue for the auctioneer. The performance of these three heuristics is evaluated in the context of a price controlled resource allocation process designed for the control and provision of distributed information services. Comparing the SG and SA method shows that depending on the problem structure the performance of the SA is up to 20% higher than the performance of the simple greedy allocation method. The proposed GA approach, using a random key encoding, results in a further improvement of the solution quality. Although the metaheuristic approaches result in higher search performance, the computational effort in terms of used CPU time is higher in comparison to the simple greedy mechanism. However, the absolute overall computation time is low enough to enable real-time execution in the considered IS application domain.
Translation of the abstract: This paper presents and compares three heuristics for the combinatorial auction problem. Besides a simple greedy (SG) mechanism, two metaheuristics, a simulated annealing (SA), and a genetic algorithm (GA) approach are developed which use the combinatorial auction process to find an allocation with maximal revenue for the auctioneer. The performance of these three heuristics is evaluated in the context of a price controlled resource allocation process designed for the control and provision of distributed information services. Comparing the SG and SA method shows that depending on the problem structure the performance of the SA is up to 20% higher than the performance of the simple greedy allocation method. The proposed GA approach, using a random key encoding, results in a further improvement of the solution quality. Although the metaheuristic approaches result in higher search performance, the computational effort in terms of used CPU time is higher in comparison to the simple greedy mechanism. However, the absolute overall computation time is low enough to enable real-time execution in the considered IS application domain. (English)
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Schwind, Michael ; Stockheim, Tim ; Rothlauf, Franz (2003) Optimization Heuristics for the Combinatorial Auction Problem. Open Access Working papers Mannheim 13 [Working paper]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item