Optimization Heuristics for the Combinatorial Auction Problem

This paper presents and compares three heuristics for the combinatorial auctionproblem. Besides a simple greedy (SG) mechanism, two metaheuristics, a simulatedannealing (SA), and a genetic algorithm (GA) approach are developedwhich use the combinatorial auction process to an allocation with maximalrevenue for the auctioneer. The performance of these three heuristics is evaluatedin the context of a price controlled resource allocation process designed for thecontrol and provision of distributed information services. Comparing the SG andSA method shows that depending on the problem structure the performance ofthe SA is up to 20% higher than the performance of the simple greedy allocationmethod.[...]