The bottleneck generalized assignment problem

The min–max version of the generalized assignment problem is considered. We introduce relaxations and show that they produce, as sub-problems, min–max versions of the multiple-choice knapsack problem and of the 0–1 knapsack problem. It is proved that such problems can be solved exactly in polynomial time. We also introduce approximate algorithms and an exact branch-and-bound procedure. Randomly generated test problems involving up to 50000 binary variables are solved exactly in acceptable running times.