Analysis of Greedy Heuristics and Weight-Coded EAs forMultidimensional Knapsack Problems and Multi-UnitCombinatorial Auctions

Until recently, multidimensional knapsack problems (MDKP)and winner determination problems (WDP) have been studiedindependently of each other, although WDPs can bemodelled as MDKPs. State-of-the-art optimization methodsfor WDPs are exact algorithms whereas MDKPs aremainly solved using heuristics or metaheuristics such as evolutionaryalgorithms (EAs). This paper compares and studiesthe performance of these different approaches for MDKPand WDP test instances. It shows that all currently usedWDP test instances can be solved optimally and in a shortlength of time by exact optimization methods. Thus, thesetest instances are only of limited usefulness for estimatingthe performance of optimization methods for the WDP.[...]