Publikationen


english Pfeiffer, Jella; Rothlauf, Franz: Greedy Heuristics and Weight-Coded EAs for Multidimensional Knapsack Problems and Multi-Unit Combinatorial Auctions, In: Nickel, S. and Kalcsics, J. (Hrsg.): Proceedings of the International Conference on Operations Research 2007, Saabrücken, Sept. 2007. Springer, 2008

Abstract

Until recently, multidimensional knapsack problems (MDKP) and winner determination problems (WDP) in combinatorial auctions have been studied independently of each other, although WDPs can be modeled as MDKPs. State-of-the-art optimization methods for WDPs are exact algorithms whereas MDKPs are mainly solved using heuristics or metaheuristics such as evolutionary algorithms (EAs). This paper compares and studies the performance of these different approaches for MDKP and WDP test instances. It shows that all currently used WDP test instances can be solved optimally and in a short length of time by exact optimization methods. Thus, these test instances are only of limited usefulness for estimating the performance of optimization methods for more complex instances of the WDP. For typical MDKP instances, exact approaches fail while simple greedy heuristics are very fast and provide high-quality solutions. The gaps towards optimal solutions are usually only a few percent and decrease with an increasing tightness ratio of the underlying MDKP. Weight-coded EAs significantly improve solution quality of greedy heuristics at the expense of much higher computational effort. However, as the main quality improvement occurs in the very early stages of EA runs, running times observed in the literature can be greatly reduced with only minor effects on the resulting solution quality.

BibTeX

@InProceedings{LsRothlauf:Pub525,
  author = \{Pfeiffer, Jella and Rothlauf, Franz},
  title = \{Greedy Heuristics and Weight-Coded EAs for Multidimensional Knapsack Problems and Multi-Unit Combinatorial Auctions},
  year = \{2008},
  editor = \{Nickel, S. and Kalcsics, J.},
  booktitle = \{Proceedings of the International Conference on Operations Research 2007},
  publisher = \{Springer},
  date = \{Sept. 2007},
}

BibTeX Download für BibTeX

Endnote

EndNote Download für EndNote