THE BOTTLENECK GENERALIZED ASSIGNMENT PROBLEM

The min-max version of the generalized assignment problem is considere d. We introduce relaxations and show that they produce, as sub-problem s, 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 e xactly in polynomial time. We also introduce approximate algorithms an d an exact branch-and-bound produce. Randomly generated test problems involving up to 50000 binary variables are solved exactly in acceptabl e running times.