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 produce. Randomly generated test problems involving up to 50000 binary variables are solved exactly in acceptable running times.