The generalized assignment problem (GAP) is a specially structured integer programming problem. Typical applications include facility location, personnel assignment, logistics and computer networking. A totally automated software package designed for solving large-scale GAP and related problems will be available for both experimental purposes and production applications. The resultant software will be a linear programming based system which incorporates a polyhedral cutting plane philosophy. This approach, which is particularly geared toward the solution of large-scale problems, is based upon the structural properties of the polytope associated with GAP. In general, current solution methods for GAP ignore the structure of the polytope; consequently, these methods tend to be appropriate only for problems of moderate size since computational requirements tend to increase very rapidly as problem size increases. The foundation for the system will depend upon constraint identification algorithms developed for three classes of facet defining inequalities which have been derived for GAP. These facet defining inequalities represent a significant extension within this area of integer programming since they are based upon combinations of knapsack constraints. On the other hand, currently available integer programming systems, which employ a polyhedral philosophy, have only considered the information embedded within individual knapsack constraints when generating inequalities.
