|
Optimization Heuristics for the Combinatorial Auction Problem
Schwind, Michael
;
Stockheim, Tim
;
Rothlauf, Franz
|
URL:
|
https://ub-madoc.bib.uni-mannheim.de/90
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-906
|
|
Dokumenttyp:
|
Arbeitspapier
|
|
Erscheinungsjahr:
|
2003
|
|
Titel einer Zeitschrift oder einer Reihe:
|
Working Papers
|
|
Band/Volume:
|
13
|
|
Ort der Veröffentlichung:
|
Mannheim
|
|
ISSN:
|
1869-0483 , 1869-0491
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Betriebswirtschaftslehre > Sonstige - Fakultät für Betriebswirtschaftslehre
|
|
MADOC-Schriftenreihe:
|
Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
|
|
Fachgebiet:
|
004 Informatik
|
|
Normierte Schlagwörter (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.
|
|
Übersetzung des Abstracts:
|
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.
(Englisch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)